Skip to main content

Leetcode 212. Word Search II. Python (TrieNode/Prefix Tree)

 212Word Search II


Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.


Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

Constraints:

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 12
  • board[i][j] is a lowercase English letter.
  • 1 <= words.length <= 3 * 104
  • 1 <= words[i].length <= 10
  • words[i] consists of lowercase English letters.
  • All the strings of words are unique.



class TrieNode:
    def __init__(self):
        self.children = {}
        self.eow = False
        self.counter = 0
    
    def wadd(self, w):
        curr = self
        curr.counter += 1
        for c in w:
            if c not in curr.children:
                curr.children[c] = TrieNode()
            curr = curr.children[c]
            curr.counter += 1
        curr.eow = True
    
    def wremove(self, w):
        curr= self
        curr.counter -= 1
        for c in w:
            if c in curr.children:
                curr = curr.children[c]
                curr.counter -= 1
    
class Solution:
    def findWords(self, b: List[List[str]], words: List[str]) -> List[str]:
        root = TrieNode()
        for w in words:
            root.wadd(w)
        
        rows, cols = len(b), len(b[0])
        ans, vs = set(), set()
        
        def dfs(r,c,n,w):
            if (r<0 or c<0 or 
                r==rows or c==cols or
               (r,c) in vs or b[r][c] not in n.children or
                n.children[b[r][c]].counter < 1):
                return
            
            vs.add((r,c))
            n = n.children[b[r][c]]
            w += b[r][c]
            if n.eow:
                n.eow = False
                ans.add(w)
                root.wremove(w)
                
            dfs(r+1,c,n,w)
            dfs(r-1,c,n,w)
            dfs(r,c+1,n,w)
            dfs(r,c-1,n,w)
            
            vs.remove((r,c))
            
        for r in range(rows):
            for c in range(cols):
                dfs(r,c,root,"")
                
        return list(ans)
            

Explaination : 









Comments

Popular posts from this blog

Leetcode 371. Sum of Two Integers. C++ / Java

371 .  Sum of Two Integers   Given two integers  a  and  b , return  the sum of the two integers without using the operators   +   and   - .   Example 1: Input: a = 1, b = 2 Output: 3 Example 2: Input: a = 2, b = 3 Output: 5   Constraints: -1000 <= a, b <= 1000 Solution :  C++ : class Solution { public: int getSum(int a, int b) { if (b==0) return a; int sum = a ^ b; int cr = (unsigned int) (a & b) << 1; return getSum(sum, cr); } }; Java :  class Solution { public int getSum(int a, int b) { while(b != 0){ int tmp = (a & b) << 1; a = a ^ b; b = tmp; } return a; } } Explaination :

Leetcode 338. Counting Bits. Python (Bubble Sort)

Given an integer  n , return  an array  ans  of length  n + 1  such that for each  i   ( 0 <= i <= n ) ,  ans[i]  is the  number of  1 's  in the binary representation of  i .   Example 1: Input: n = 2 Output: [0,1,1] Explanation: 0 --> 0 1 --> 1 2 --> 10 Example 2: Input: n = 5 Output: [0,1,1,2,1,2] Explanation: 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101   Constraints: 0 <= n <= 10 5   Follow up: It is very easy to come up with a solution with a runtime of  O(n log n) . Can you do it in linear time  O(n)  and possibly in a single pass? Can you do it without using any built-in function (i.e., like  __builtin_popcount  in C++)?   Solution : class Solution:     def countBits(self, n: int) -> List[int]:         dp = [0] * (n+1)         c = 1        ...

Number of Connected Components in an Undirected Graph (Python)

66.  Number of Connected Components in an Undirected Graph Question Link :  check here Givennnodes labeled from0ton - 1and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph. Example 1:      0          3      |          |      1 --- 2    4 Givenn = 5andedges = [[0, 1], [1, 2], [3, 4]], return2. Example 2:      0           4      |           |      1 --- 2 --- 3 Givenn = 5andedges = [[0, 1], [1, 2], [2, 3], [3, 4]], return1. Note: You can assume that no duplicate edges will appear inedges. Since all edges are undirected,[0, 1]is the same as[1, 0]and thus will not appear together inedges. Solution : class Solution: def counComponents(self, n: int, edges : List[List[int]]) -> i...