DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Please enter at least three characters to search
Refcards Trend Reports
Events Video Library
Refcards
Trend Reports

Events

View Events Video Library

Zones

Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks

The software you build is only as secure as the code that powers it. Learn how malicious code creeps into your software supply chain.

Apache Cassandra combines the benefits of major NoSQL databases to support data management needs not covered by traditional RDBMS vendors.

Generative AI has transformed nearly every industry. How can you leverage GenAI to improve your productivity and efficiency?

Modernize your data layer. Learn how to design cloud-native database architectures to meet the evolving demands of AI and GenAI workloads.

Related

  • Universal Implementation of BFS, DFS, Dijkstra, and A-Star Algorithms
  • Queue in Data Structures and Algorithms
  • Effective Java Collection Framework: Best Practices and Tips
  • Python Stack Data Structure: A Versatile Tool for Real-time Applications

Trending

  • Performing and Managing Incremental Backups Using pg_basebackup in PostgreSQL 17
  • A Deep Dive Into Firmware Over the Air for IoT Devices
  • Agentic AI for Automated Application Security and Vulnerability Management
  • Why Database Migrations Take Months and How to Speed Them Up
  1. DZone
  2. Data Engineering
  3. Data
  4. Programming Solutions for Graph and Data Structure Problems With Implementation Examples (Word Dictionary)

Programming Solutions for Graph and Data Structure Problems With Implementation Examples (Word Dictionary)

This article provides programming solutions and implementation examples for various graph and data structure problems.

By 
Volha Kurcheuskaya user avatar
Volha Kurcheuskaya
·
Mar. 22, 23 · Tutorial
Likes (1)
Comment
Save
Tweet
Share
2.1K Views

Join the DZone community and get the full member experience.

Join For Free

This article provides programming solutions and implementation examples for various graph and data structure problems. Graphs and data structures are fundamental concepts in computer science, and understanding them is crucial for developing efficient algorithms for a wide range of applications.

This article covers several common graph problems, including finding a path between two nodes in a directed graph and designing a data structure that supports adding new words and searching for matching words. For each problem, we provide a detailed explanation of the solution approach and then provide an implementation in Kotlin programming language.

Whether you are a beginner or an experienced programmer, this article will provide valuable insights and knowledge on tackling complex graph and data structure problems. By the end of this article, you will have a deeper understanding of these fundamental concepts and be able to apply them to solve more advanced programming problems.

I propose to consider one problem.

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

  • WordDictionary() Initializes the object.
  • void addWord(word) Adds word to the data structure, it can be matched later.
  • bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

In this problem, we are asked to design a data structure that can efficiently store a collection of words and perform queries to check if a given the word matches any previously added word. Specifically, the data structure should support two operations: adding a word and searching for a word.

To add a word to the data structure, we will use a trie, which is a tree-like data structure that stores a collection of strings. Each node in the trie represents a single character of a string, and we can store a flag at the end of each string to indicate that it is a complete word.

To search for a word, we will perform a depth-first search on the trie. If the current character of the word is a letter, we follow the corresponding edge in the trie. If the current character is a dot, we follow all outgoing edges from the current node. If we reach the end of the word and the flag at the current node is set, then we have found a match.

With this approach, we can efficiently store a collection of words and quickly search for matches. In the implementation, we will use a TrieNode class to represent each node in the trie, and we will define methods to add a word and search for a word in the WordDictionary class.

We can use a trie data structure to store the words to solve this problem. Each node in the trie represents a letter, and we can store a flag at the end of each word to indicate that it is a complete word. When adding a word, we start at the root of the trie and add nodes for each letter in the word. Once we reach the end of the word, we set the flag to indicate that it is a complete word.

To search for a word, we can perform a depth-first search on the trie. If the current character of the word is a letter, we follow the corresponding edge in the trie. If the current character is a dot, we follow all outgoing edges from the current node. If we reach the end of the word and the flag at the current node is set, then we have found a match.

Here's an implementation of the WordDictionary class in Kotlin:

 
class WordDictionary() {



    private class TrieNode {

        val children = HashMap<Char, TrieNode>()

        var isCompleteWord = false

    }



    private val root = TrieNode()



    fun addWord(word: String) {

        var current = root

        for (char in word) {

            val child = current.children.getOrPut(char) { TrieNode() }

            current = child

        }

        current.isCompleteWord = true

    }



    fun search(word: String): Boolean {

        return searchHelper(word, 0, root)

    }



    private fun searchHelper(word: String, index: Int, node: TrieNode): Boolean {

        if (index == word.length) {

            return node.isCompleteWord

        }

        val char = word[index]

        if (char == '.') {

            for (child in node.children.values) {

                if (searchHelper(word, index + 1, child)) {

                    return true

                }

            }

        } else {

            val child = node.children[char]

            if (child != null && searchHelper(word, index + 1, child)) {

                return true

            }

        }

        return false

    }

}


The WordDictionary class has a private inner class TrieNode, which represents a node in the trie. Each TrieNode has a map of children, where the key is a character, and the value is another TrieNode. It also has a boolean flag isCompleteWord, to indicate if a word ends at the current node.

The WordDictionary class has two methods: addWord and search. The addWord method takes a word as input and adds it to the trie. The search method takes a word as input and returns true if there is any string in the data structure that matches the word or false otherwise. The search method uses a recursive helper function searchHelper, to perform the depth-first search on the trie.

Here's another implementation example in Kotlin for the WordDictionary problem using a HashMap and recursion:

 
class WordDictionary() {

    private val root = HashMap<Char, Any>()



    fun addWord(word: String) {

        var node = root

        for (c in word) {

            node = node.computeIfAbsent(c) { HashMap<Char, Any>() } as HashMap<Char, Any>

        }

        node.putIfAbsent('\u0000', Any())

    }



    fun search(word: String): Boolean {

        return searchHelper(word, 0, root)

    }



    private fun searchHelper(word: String, index: Int, node: HashMap<Char, Any>): Boolean {

        if (index == word.length) {

            return node.containsKey('\u0000')

        }

        val c = word[index]

        if (c != '.') {

            val next = node[c] as? HashMap<Char, Any> ?: return false

            return searchHelper(word, index + 1, next)

        }

        for (next in node.values) {

            if (next is HashMap<*, *>) {

                if (searchHelper(word, index + 1, next as HashMap<Char, Any>)) {

                    return true

                }

            }

        }

        return false

    }

}


This implementation uses a HashMap to store the trie, where each key is a character, and each value is another HashMap representing the children nodes. We use recursion to search the trie for a matching word, where we compare the current character to the trie node and follow the appropriate path. For example, if the current character is a dot, we recursively check all possible children nodes. Finally, we check if the node at the end of the word contains the flag '\u0000' to indicate a complete word.

Each of the solutions described above for the WordDictionary problem has its own advantages and disadvantages.

The first solution using a Trie data structure is efficient in terms of both time and space complexity. It provides fast lookup times and has a relatively small memory footprint. However, implementing a Trie from scratch can be challenging, and the code can be difficult to read and understand.

The second solution using a HashMap and recursion, is also efficient and provides a simpler and more readable implementation. However, it may not be as space-efficient as the Trie solution, as it requires storing every character in a separate HashMap.

Ultimately, the choice between these solutions depends on the specific requirements of the problem at hand, such as the expected size of the input and the performance constraints. However, both solutions are valid and can provide efficient and effective solutions to the WordDictionary problem in Kotlin.

Data structure Implementation Data (computing) Graph (Unix) Kotlin (programming language)

Opinions expressed by DZone contributors are their own.

Related

  • Universal Implementation of BFS, DFS, Dijkstra, and A-Star Algorithms
  • Queue in Data Structures and Algorithms
  • Effective Java Collection Framework: Best Practices and Tips
  • Python Stack Data Structure: A Versatile Tool for Real-time Applications

Partner Resources

×

Comments
Oops! Something Went Wrong

The likes didn't load as expected. Please refresh the page and try again.

ABOUT US

  • About DZone
  • Support and feedback
  • Community research
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Core Program
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 3343 Perimeter Hill Drive
  • Suite 100
  • Nashville, TN 37211
  • support@dzone.com

Let's be friends:

Likes
There are no likes...yet! 👀
Be the first to like this post!
It looks like you're not logged in.
Sign in to see who liked this post!