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.
·
Join the DZone community and get the full member experience.
Join For FreeThis 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)Addswordto the data structure, it can be matched later.bool search(word)Returnstrueif there is any string in the data structure that matcheswordorfalseotherwise.wordmay 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.
Opinions expressed by DZone contributors are their own.
Comments