CONY的世界

211. Add and Search Word - Data structure design

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

For example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Success:

278 ms, beats 78.66 % of python submissions

這題看到本來有人要用trie，但是我想一想覺得不用這麼複雜，因為這是one by one 的尋找啊，只要對應位置對就好，所以就自己寫了
add() 做個dict 以 word length 為key，value 為 list 放著各個add的值 ，
search() 就依照要搜尋的word len call 出對應存入的list 後，判斷是否相等，到最後都沒跳開表示字串完全吻合  return True，
如果有word 非“.” 然後跟dic的word 又不同，表示不吻合 return False
如果dict 裡面值都搜尋完都沒有符合的，表示找不到，所以也 return False 

然後這邊注意一下一個 list append function

self.slist[len(word)].append(word) 

這邊不需要 assign 就會將word append 到 self.slist[len(word)] list 內了
千萬不要像我之前debug 失智還

self.slist[len(word)] ＝ self.slist[len(word)].append(word)

這只會把list 又覆寫清空啊......

class WordDictionary(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.slist = {0:[]}
        

    def addWord(self, word):
        """
        Adds a word into the data structure.
        :type word: str
        :rtype: void
        """
        print word, len(word) in self.slist
        if len(word) not in self.slist:
            self.slist[len(word)] = [word]
        else:
            self.slist[len(word)].append(word) 
            


    def search(self, word):
        """
        Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
        :type word: str
        :rtype: bool
        """
        for s in self.slist[len(word)] if len(word) in self.slist else []:
            #print s, word
            for index in range(len(word)):
                if word[index] != "." and word[index] != s[index]:
                    break
                if index == len(word)-1:
                    return True 
        return False


# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)

79. Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board = 

[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

 這題很像是當初演算法最後一個作業，像是candy crush 一樣，找符合的字串

會了想節省programming 我就會想說要用hash table 去減少不斷讀值，可惜方向是錯了
因為這樣做好像也沒有比較快，
看到的官解是用dfs ，有人用dynamic programming 的方式去比對，但是那算很慢
直接用innfer function 來算，快又簡單

然後做到這題的時候要考量到走的時候走過的值不能再走，但是新路線時這些記錄要全部清空
所以去查了一下python pass parameter 的方式，以下是網路解釋

Python passes references-to-objects by value (like Java), and everything in Python is an object.  

 

Success:

262 ms, beats 89.26 % of python submissions

比較乾淨的寫法

class Solution(object):

    def exist(self, board, word):
        L= len(word)
        # if not L: return True
        M = len(board)
        # if not M: return False
        N = len(board[0])
        def DFS(i, j, l):
            if board[i][j] != word[l]: return False
            if l+1 == L: return True
            board[i][j] += '@'
            hasFound = (i-1>=0 and DFS(i-1, j, l+1)) or (i+1 < M and DFS(i+1, j, l+1)) or\
                (j-1 >= 0 and DFS(i, j-1, l+1)) or (j+1 < N and DFS(i, j+1, l+1))
            board[i][j] = board[i][j][0] #backtrace
            return hasFound
        
        for i in range(M):
            for j in range(N):
                if DFS(i,j, 0):
                    return True
        return False

Fail:

class Solution(object):
    def createdic(self, board):
        self.dict = {}
        for row in range(len(board)):
            for col in range(len(board[0])):
                if board[row][col] in self.dict:
                    self.dict[board[row][col]].append((row, col)) 
                else:
                    self.dict[board[row][col]] = [(row, col)]
                    
    def nextpoint_pos(self, start, pool):
        if not start or not pool:
            return []
        res, move = [], [(0,1),(0,-1),(1,0),(-1,0)] 
        for i in range(len(start)):
            for j in range(len(move)):
                neighbor = (start[i][0]+move[j][0],start[i][1]+move[j][1])                                     
                if neighbor in pool:
                    res.append(neighbor) 
        return res
    
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        self.createdic(board)
        result = self.dict[word[0]] if word[0] in self.dict else[]
        for index in range(0,len(word)-1):
            if word[index+1] in self.dict:
                result = self.nextpoint_pos(result, self.dict[word[index+1]])
            else:
                return False
        return True if len(result) > 0 else False