Leetcode Pattern 13 Trie

1. Initialize: cur = root
2. for each char c in target string S:
3.      if cur does not have a child c:
4.          cur.children[c] = new Trie node
5.      cur = cur.children[c]
6. cur is the node which represents the string S

1. Initialize: cur = root
2. for each char c in target string S:
3.   if cur does not have a child c:
4.     search fails
5.   cur = cur.children[c]
6. search successes

class TrieNode:
    def __init__(self):
        self.isEnd = False
        self.children = {}

class Trie:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if not (ch in node.children):
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.isEnd = True
        return

    def search(self, word: str) -> bool:
        node = self.root
        for ch in word:
            if ch in node.children:
                node = node.children[ch]
            else:
                return False
        return node.isEnd


    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for ch in prefix:
            if ch in node.children:
                node = node.children[ch]
            else:
                return False
        return True

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isEnd = False

class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.isEnd = True
        return

    def search_helper(self, node: TrieNode, word: str) -> bool:
        # Reach end
        if not word:
            return node.isEnd
        char = word[0]
        if char == ".":
            for char in node.children:
                if self.search_helper(node.children[char], word[1:]):
                    return True
        elif char in node.children:
            return self.search_helper(node.children[char], word[1:])
        return False

    def search(self, word: str) -> bool:
        return self.search_helper(self.root, word)

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isEnd = False
        self.word = None

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str):
        node = self.root
        for ch in word:
            if not (ch in node.children):
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.isEnd = True
        node.word = word

    def search(self, word: str):
        node = self.root
        for ch in word:
            if ch in node.children:
                node = node.children[ch]
            else:
                return False
        return node.isEnd

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        trie = Trie()
        for word in words:
            trie.insert(word)
        m = len(board)
        n = len(board[0])
        def getNeighbors(i, j):
            ans = []
            for diff in [(1, 0), (-1, 0), (0, -1), (0, 1)]:
                n_i = i + diff[0]
                n_j = j + diff[1]
                if (n_i >= 0) and (n_i < m) and (n_j >= 0) and (n_j < n):
                    ans.append((n_i, n_j))
            return ans
        ans = set([])
        def dfs(i, j, node):
            c = board[i][j]
            if c in node.children:
                nextNode = node.children[c]
                board[i][j] = " "
                if nextNode.isEnd:
                    ans.add(nextNode.word)
                neighbors = getNeighbors(i, j)
                for neighbor in neighbors:
                    if board[neighbor[0]][neighbor[1]] != " ":
                        dfs(neighbor[0], neighbor[1], nextNode)
                board[i][j] = c
        for i in range(m):
            for j in range(n):
                dfs(i, j, trie.root)
        return list(ans)

# check Pattern 21 Palindrome

class TrieNode:
    def __init__(self):
        self.children = {}
        # Stores the index of the word if this node represents the last letter of a word.
        self.word_end_index = -1
        # Stores indices of words such that the substring from the current node to the end of the word forms a palindrome.
        self.palindrome_suffix_indices = []

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word, index):
        node = self.root
        for i, char in enumerate(word):
            if is_palindrome(word, i, len(word) - 1):
                node.palindrome_suffix_indices.append(index)
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.word_end_index = index

    # Finds all palindrome pairs that can be formed by the given word. It traverses the Trie and checks for palindromic conditions.
    def find_palindromes_with_suffix(self, word, index):
        result = []
        current = self.root
        for j in range(len(word)):
            if current.word_end_index != -1 and current.word_end_index != index and is_palindrome(word, j, len(word) - 1):
                result.append([index, current.word_end_index])
            if word[j] not in current.children:
                return result
            current = current.children[word[j]]
        for palindrome_index in current.palindrome_suffix_indices:
            if palindrome_index != index:
                result.append([index, palindrome_index])
        if current.word_end_index != -1 and current.word_end_index != index:
            result.append([index, current.word_end_index])
        return result

# check the word[start: end + 1] is palindrome
def is_palindrome(word, start, end):
    while start < end:
        if word[start] != word[end]:
            return False
        start += 1
        end -= 1
    return True

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        trie = Trie()
        for i, word in enumerate(words):
            # word[::-1] reverse word
            trie.insert(word[::-1], i)

        pairs = []
        for i, word in enumerate(words):
            # extend: Add multiple results
            pairs.extend(trie.find_palindromes_with_suffix(word, i))

        return pairs

FileSystem() Initializes the object of the system.
List<String> ls(String path)

class TrieNode:
    def __init__(self, name):
        self.name = name
        self.isFile = False
        self.fileContent = ""
        self.children = {}

class Trie(object):
    def __init__(self):
        self.root = TrieNode("")
    def insert(self, path, isFile):
        node = self.root
        folders = path[1:].split("/")
        for i in range(len(folders)):
            if folders[i] in node.children:
                node = node.children[folders[i]]
            else:
                new_node = TrieNode(folders[i])
                node.children[folders[i]] = new_node
                node = new_node
        if isFile:
            node.isFile = True
        return node
    def query(self, path):
        node = self.root
        folders = path[1:].split("/")
        #print("query: {}".format(path))
        for i in range(len(folders)):
            if folders[i] in node.children:
                node = node.children[folders[i]]
        if node.isFile:
            return [node.name]
        filesFolders = list(node.children.keys())
        #print(filesFolders)
        filesFolders.sort()
        return filesFolders

class FileSystem:

    def __init__(self):
        self.trie = Trie()

    def ls(self, path: str) -> List[str]:
        #print("ls: {}".format(path))
        return self.trie.query(path)

    def mkdir(self, path: str) -> None:
        self.trie.insert(path, False)

    def addContentToFile(self, filePath: str, content: str) -> None:
        node = self.trie.insert(filePath, True)
        node.fileContent += content

    def readContentFromFile(self, filePath: str) -> str:
        node = self.trie.insert(filePath, False)
        return node.fileContent


# Your FileSystem object will be instantiated and called as such:
# obj = FileSystem()
# param_1 = obj.ls(path)
# obj.mkdir(path)
# obj.addContentToFile(filePath,content)
# param_4 = obj.readContentFromFile(filePath)

class TrieNode:
    def __init__(self, char):
        self.char = char
        self.isEnd = False
        self.count = 0
        self.children = {}

class Trie(object):
    def __init__(self):
        self.root = TrieNode("")

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch in node.children:
                node = node.children[ch]
            else:
                new_node = TrieNode(ch)
                node.children[ch] = new_node
                node = new_node
        node.isEnd = True
        node.count += 1

    def dfs(self, node, prefix):
        if node.isEnd:
            self.output.append((prefix + node.char, node.count))
        for ch in node.children:
            self.dfs(node.children[ch], prefix + node.char)

    def query(self, prefix):
        self.output = []
        node = self.root
        for ch in prefix:
            if ch in node.children:
                node = node.children[ch]
            else:
                return []
        # remove last ch because node contains it.
        self.dfs(node, prefix[:-1])
        return self.output

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        n = len(products)
        trie = Trie()
        words = set(products)
        for i in range(n):
            trie.insert(products[i])
        ans = []
        for i in range(len(searchWord)):
            res = trie.query(searchWord[:i + 1])
            res = list(map(lambda r: r[0], res))
            res.sort()
            if len(res) > 3:
                res = res[:3]
            #print(res)
            ans = ans + [res]
        return ans

class TrieNode:
    def __init__(self):
        self.isEnd = False
        self.children = {}
        self.val = None

class MapSum:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, key: str, val: int) -> None:
        node = self.root
        for ch in key:
            if not (ch in node.children):
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.isEnd = True
        node.val = val

    def calculateSum(self, node: TrieNode) -> int:
        total = node.val if node.isEnd else 0
        for ch in node.children:
            total += self.calculateSum(node.children[ch])
        return total

    def sum(self, prefix: str) -> int:
        node = self.root
        for ch in prefix:
            if ch in node.children:
                node = node.children[ch]
            else:
                return 0
        return self.calculateSum(node)

class TrieNode:
    def __init__(self):
        self.isEnd = False
        self.children = {}

class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if not (ch in node.children):
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.isEnd = True
    def search(self, word: str) -> str:
        node = self.root
        if not word[0] in node.children:
            return word
        ans = ""
        isEnd = False
        for ch in word:
            if node.isEnd:
                return ans
            if not ch in node.children:
                return word
            node = node.children[ch]
            ans += ch
        return ans

class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        trie = Trie()
        for word in dictionary:
            trie.insert(word)
        ans = []
        for word in sentence.split(" "):
            ans.append(trie.search(word))
        return " ".join(ans)

AutocompleteSystem(String[] sentences, int[] times) Initializes the object with the sentences and times arrays.
List<String> input(char c) This indicates that the user typed the character c.

class TrieNode:
    def __init__(self):
        self.isEnd = False
        self.searchTime = 0
        self.children = {}

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> TrieNode:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.isEnd = True
        return node

    def search(self, prefix: str) -> TrieNode:
        node = self.root
        for ch in prefix:
            if ch in node.children:
                node = node.children[ch]
            else:
                return None
        return node

    def traverse(self, node: TrieNode, prefix: str) -> int:
        ans = []
        if node.isEnd:
            ans = [(node.searchTime, prefix)]
        for ch in node.children:
            ans += self.traverse(node.children[ch], prefix + ch)
        return ans

class AutocompleteSystem:

    def __init__(self, sentences, times):
        n = len(sentences)
        self.trie = Trie()
        for i in range(n):
            endNode = self.trie.insert(sentences[i])
            endNode.searchTime = times[i]
        self.searchString = ""

    def input(self, c: str):
        if (c == "#"):
            node = self.trie.insert(self.searchString)
            node.searchTime += 1
            self.searchString = ""
            return []

        self.searchString += c
        node = self.trie.search(self.searchString)
        if node is None:
            return []
        results = self.trie.traverse(node, self.searchString)
        results = sorted(results, key=lambda x: (-x[0], x[1]))
        if len(results) > 3:
            results = results[:3]
        return list(map(lambda result: result[1], results))

class TrieNode:
    def __init__(self):
        self.children = {}

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, num):
        node = self.root
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            if bit not in node.children:
                node.children[bit] = TrieNode()
            node = node.children[bit]

    def find_max_xor(self, num):
        node = self.root
        max_xor = 0
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            toggled_bit = 1 - bit
            if toggled_bit in node.children:
                max_xor = (max_xor << 1) | 1
                node = node.children[toggled_bit]
            else:
                max_xor = max_xor << 1
                node = node.children[bit]
        return max_xor

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        trie = Trie()
        max_xor = 0

        # Insert all numbers into the Trie
        for num in nums:
            trie.insert(num)

        # Find the maximum XOR for each number
        for num in nums:
            max_xor = max(max_xor, trie.find_max_xor(num))

        return max_xor

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        # Initialize the maximum XOR value
        max_xor = 0
        # Initialize the mask
        mask = 0

        # Iterate over the bit positions from 31 to 0
        for i in range(31, -1, -1):
            # Update the mask to consider the next bit
            mask |= (1 << i)
            # Use a set to store prefixes of the numbers with the current mask
            prefixes = set()
            for num in nums:
                prefixes.add(num & mask)

            # Try to form the new maximum XOR with the current bit set to 1
            new_max_xor = max_xor | (1 << i)

            # Check if there are two prefixes that can form the new_max_xor
            for prefix in prefixes:
                if (prefix ^ new_max_xor) in prefixes:
                    max_xor = new_max_xor
                    break

        return max_xor

class TrieNode:
    def __init__(self):
        self.isEnd = False
        self.children = {}
        self.words = []

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
            node.words.append(word)
        node.isEnd = True

    def search_words_with_prefix(self, prefix: str) -> bool:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return []
            node = node.children[ch]
        return node.words

class Solution:
    def wordSquares(self, words: List[str]) -> List[List[str]]:
        trie = Trie()
        for word in words:
            trie.insert(word)

        results = []
        n = len(words[0])
        def build_square(step):
            if step == n:
                results.append(square[:])
                return
            prefix = ''.join(square[i][step] for i in range(step))
            for candidate in trie.search_words_with_prefix(prefix):
                square.append(candidate)
                build_square(step + 1)
                square.pop()

        square = []
        for word in words:
            square.append(word)
            build_square(1)
            square.pop()

        return results