23.03.19 Today’s Leetcode

211. Design Add and Search Words Data Structure (medium)

Trie Approach

class WordDictionary:

    def __init__(self):
        self.d = {}

    def addWord(self, word: str) -> None:
        n = len(word)
        def dfs(cur, index):
            if index >= n:
                cur['*'] = 1
                return
            for i in range(index, n):
                char = word[i]
                if char not in cur: cur[char] = {}
                if '.' not in cur: cur['.'] = {}
                dfs(cur[char], index + 1)
                dfs(cur['.'], index + 1)
            # print(cur)

        dfs(self.d, 0)
        # print(self.d)

    def search(self, word: str) -> bool:
        cur = self.d
        for char in word:
            if char not in cur:
                return False
            cur = cur[char]
        return '*' in cur and cur['*'] == 1


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

Simple Approach

class WordDictionary:

    def __init__(self):
        self.d = set()

    def addWord(self, word: str) -> None:
        self.d.add(word)

    def search(self, word: str) -> bool:
        if '.' not in word:
            if word in self.d:
                return True
        else:
            n = len(word)
            for temp in self.d:
                if len(temp) != n: continue
                ans = True
                for i in range(n):
                    if word[i] == '.': continue
                    if word[i] != temp[i]:
                        ans = False
                        break
                if ans:
                    return True
            return False

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

316. Remove Duplicate Letters (medium)

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        last_visited = {}
        stack = []
        visited = set()

        for i in range(len(s)):
            last_visited[s[i]] = i	
        
        for i in range(len(s)):
            if s[i] in visited: continue
            while (stack and stack[-1] > s[i] and last_visited[stack[-1]] > i):
                visited.remove(stack.pop())
            stack.append(s[i])
            visited.add(s[i])

        return ''.join(stack)