[LeetCode] 1032. Stream of Characters

 Problem : https://leetcode.com/problems/stream-of-characters/

This is an obvious Tire problem. It is difficult because it is hard to realize the edge cases at the first place.

We cannot assume one input word cannot be prefix of another input word.

Such as:  ["ab","ba","aaab","abab","baa"]

To cover all cases, we need to remember the last pointer of all valid prefixes.

class TrieNode {
    char letter = 0;
    boolean end = false;
    HashMap<Character, TrieNode> children = new HashMap();
}

class StreamChecker {
    TrieNode root = new TrieNode();
    Queue<TrieNode> queue = new LinkedList();
    
    public StreamChecker(String[] words) {
        for (int i = 0; i < words.length; i++) {
            TrieNode p = root;
            
            for (int j = 0; j < words[i].length(); j++) {
                if (p.children.containsKey(words[i].charAt(j))) {
                    p = p.children.get(words[i].charAt(j));
                } else {
                    TrieNode tmp = new TrieNode();
                    tmp.letter = words[i].charAt(j);
                    p.children.put(words[i].charAt(j), tmp);
                    p = tmp;
                }
            }
            
            p.end = true;
        }
    }
    
    public boolean query(char letter) {
        queue.offer(root);
        
        boolean found = false;
        Queue<TrieNode> next = new LinkedList();
        
        while (!queue.isEmpty()) {
            TrieNode p = queue.poll();
            
            if (p.children.containsKey(letter)) {
                next.offer(p.children.get(letter));
                if (p.children.get(letter).end) {
                    found = true;
                }
            }
        }
        
        queue = next;
        return found;
    }
}

However this process is not optimized.

A better solution is saving the prefixes backwards in Trie. Because all potential valid prefixes end with the same letter.

class TrieNode:
    def __init__(self, w = None):
        self.w = w
        self.children = {}
        self.end = False

class StreamChecker:

    def __init__(self, words: List[str]):
        self.root = TrieNode()
        self.max_len = 0
        self.stream = deque()
        
        for word in words:
            self.max_len = max(self.max_len, len(word))
            
            p = self.root
            
            for w in word[::-1]:
                if w not in p.children:
                    trie = Trie(w)
                    p.children[w] = trie
                    p = trie
                else:
                    p = p.children[w]
            
            p.end = True
                      

    def query(self, letter: str) -> bool:
        self.stream.append(letter)
        
        while len(self.stream) > self.max_len:
            self.stream.popleft()
        
        p = self.root
        
        for w in reversed(self.stream):
            
            if w in p.children:
                p = p.children[w]
                if p.end:
                    return True
            else:
                return False
                
        return False

[LeetCode] 336. Palindrome Pairs

 Problem : https://leetcode.com/problems/palindrome-pairs/

There are 3 cases can form a palindrome string.

1)  ABC + CBA

2)  CBA + [A-Palindrome-String] ABC 

3)  ABC[A-Palindrome-String]  + CBA   

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        
        def isPalindrome(w, left, right):
            while left < right:
                if w[left] != w[right]: return False
                left += 1
                right -= 1
            
            return True
        
        
        result = []
        seen = { k : v for v, k in enumerate(words) }
        lens = sorted({len(w) for w in words})
        
        for i, w in enumerate(words):
            # rw = reversed 'w'
            rw = w[::-1]
            
            # case abc -- cba
            if rw in seen and seen[rw] != i:
                result.append([i, seen[rw]])
                
            l = 0
            while lens[l] < len(rw):
                # case cba  -- ddabc                
                if isPalindrome(rw, 0, len(rw) - lens[l] - 1) and \
                   rw[len(w) - lens[l]:] in seen:
                    
                    result.append([i, seen[rw[len(w) - lens[l]:]]])
                # case abcdd -- cba
                if isPalindrome(rw, lens[l], len(rw)-1) and \
                   rw[:lens[l]] in seen:
                    result.append([seen[rw[:lens[l]]], i])
                
                l += 1
        
        return result

Use Trie to find possible suffix.

class TrieNode:
    def __init__(self, val):
        self.val = val
        self.index = -1
        self.nodes = {}


class Trie:
    def __init__(self):
        self.root = TrieNode('')
    
    def add(self, index, word):
        if not word:
            self.root.index = index
        else:
            p = self.root
            
            for w in word:
                if w in p.nodes:
                    p = p.nodes[w]
                else:
                    node = TrieNode(w)
                    p.nodes[w] = node
                    p = node
                    
            p.index = index
        
def isPalindrome(word):
    if not word: return True
    
    left, right = 0, len(word)-1
    
    while left < right and word[left] == word[right]:
        left += 1
        right -=1 
    
    return left >= right

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        trie = Trie()
        
        for index, word in enumerate(words):
            trie.add(index, word[::-1])
        
        result = []
        
        for index, word in enumerate(words):
            i = 0
            p = trie.root
                        
            # dfs
            stack = [(p, "")]
            
            while stack:
                p, suffix = stack.pop()
                
                if p.index != -1 and p.index != index and isPalindrome(word[i:] + suffix):
                    result.append((index, p.index))
                
                if not suffix and i < len(word) and word[i] in p.nodes:
                    stack.append((p.nodes[word[i]], ""))
                    i += 1
                else:
                    for n in p.nodes.values():
                        stack.append((n, n.val + suffix))
        return result

Edited on 06/13/2021. Add the Trie based solution.

[LeetCode] 212. Word Search II

Problem : https://leetcode.com/problems/word-search-ii/

Tire + Backtracking approach :

class Node:
    def __init__(self, val='', end=False):
        self.val = val
        self.end = end
        self.nxt = {}

class Trie:
    def __init__(self):
        self.root = Node()
    
    def add(self, word):
        p = self.root
        
        for w in word:
            if w not in p.nxt:
                p.nxt[w] = Node(w)
            
            p = p.nxt[w]
            
        p.end = True
        

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        ROW = len(board)
        COLUMN = len(board[0])
        
        trie = Trie()
        
        for word in words:
            trie.add(word)
        
        result = set()
        visited = [[False] * COLUMN for _ in range(ROW)]
        
        def dfs(y, x, tmp, p):
            if p.end:
                result.add(tmp)
            
            for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                ny, nx = y + dy, x + dx
                
                if 0 <= ny < ROW and 0 <= nx < COLUMN and not visited[ny][nx] and board[ny][nx] in p.nxt:
                    visited[ny][nx] = True
                    dfs(ny, nx, tmp + board[ny][nx], p.nxt[board[ny][nx]])
                    visited[ny][nx] = False
        
        for y in range(ROW):
            for x in range(COLUMN):
                if board[y][x] in trie.root.nxt:
                    visited[y][x] = True
                    dfs(y, x, board[y][x], trie.root.nxt[board[y][x]])
                    visited[y][x] = False
        
        return result

Edited on 10/9/2021. Update for simpler code.

[LeetCode] 211. Design Add and Search Words Data Structure

 Problem : https://leetcode.com/problems/design-add-and-search-words-data-structure/

Trie ( prefix tree ) approach : 

class Node:
    def __init__(self, w = None):
        self.w = w
        self.children = {}
        self.end = False
            
class WordDictionary:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        
        self.trie = Node()
        self.maxLen = 0
        

    def addWord(self, word: str) -> None:
        """
        Adds a word into the data structure.
        """
        
        self.maxLen = max(self.maxLen, len(word))
        p = self.trie
        
        for w in word:
            if w in p.children:
                p = p.children[w]
            else:
                tmp = Node(w)
                p.children[w] = tmp
                p = tmp
            
        p.end = True

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
        """
        
        def dfs(i, p):
            if i >= len(word):
                return p.end
            
            w = word[i]
                
            if w == '.':
                for k in p.children:
                    if dfs(i + 1, p.children[k]):
                        return True
                    
            elif w in p.children:
                return dfs(i + 1, p.children[w])
                    
            return False
        
        return dfs(0, self.trie) if len(word) <= self.maxLen else False

[LeetCode] 208. Implement Trie (Prefix Tree)

Problem : https://leetcode.com/problems/implement-trie-prefix-tree/

One node of Trie represents a letter of the inserted words.

To search an inserted word, the code travels from the root node and find if current letter is represented by one of the child node.  When reach to the last letter of the given word, check if  Node.end = True.

class Node:
    def __init__(self, val = '', end = False):
        self.val = val
        self.end = end
        self.nxt = {}

class Trie:

    def __init__(self):
        self.root = Node()
        
    def insert(self, word: str) -> None:
        p = self.root
        
        for w in word:
            if w not in p.nxt:
                p.nxt[w] = Node(w)
            
            p = p.nxt[w]
        
        p.end = True
                
    def search(self, word: str) -> bool:
        p = self.root
        
        for w in word:
            if w not in p.nxt:
                return False
            p = p.nxt[w]
        
        return p.end

    def startsWith(self, prefix: str) -> bool:
        p = self.root
        
        for w in prefix:
            if w not in p.nxt:
                return False
            p = p.nxt[w]
        
        return True

# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

Edited on 10/08/2021. Tidy the implementation.