Practice #007: Leetcode

Leetcode: 1047. Remove All Adjacent Duplicates In String

Problem Statement

Keep a stack with the chars on the answer. For each new char from the input, pop the stack if it matches its top, or add it to the stack. 

class Solution:
    def removeDuplicates(self, s: str) -> str:
        ans = []
        for c in s:
            if len(ans) > 0 and ans[-1] == c:
                ans.pop()
            else:
                ans.append(c)
        return "".join(ans)


assert Solution().removeDuplicates("abbaca") == "ca"
assert Solution().removeDuplicates("azxxzy") == "ay"

Leetcode: 1087. Brace Expansion

Problem Statement

As the problem asks for all permutations, then it will be fine to generate each on of them efficiently. Recur over each possible character building the final string, and store the built word on the end of the recursion. Space complexity is \(O(n)\) while time complexity is \(O(n \times 3^{n/7})\) since max words generated will require groups with exactly 3 options: 

return [("Base", "Max Words")] + [
    (b, b ** (50 // (b + b - 1 + 2))) for b in [2, 3, 4, 5]
]

from typing import List


class Solution:
    def expand(self, s: str) -> List[str]:
        n = len(s)
        ans = []

        def dfs(i, cur):
            if i == n:
                ans.append(cur)
                return
            if s[i] == "{":
                j = s.index("}", i)
                for c in sorted(s[i + 1 : j].split(",")):
                    dfs(j + 1, cur + c)
            else:
                dfs(i + 1, cur + s[i])

        dfs(0, "")
        return ans


assert Solution().expand("{a,b}c{d,e}f") == ["acdf", "acef", "bcdf", "bcef"]
assert Solution().expand("abcd") == ["abcd"]

Leetcode: 1032. Stream of Characters

Problem Statement

Retrospective: I didn't solve this problem during the practice, but I thought about creating a trie with the words reversed. I didn't went deep on the idea and searched for other ways to solve. After that, I got caught on making a solution using prefix arrays for each word but with \(O(n)\) for each query which resulted on time limit exceeded.

The operation query should be efficient (faster than \(O(n)\)). Construct a Trie with the words in the dictionary reversed. Add each char from the query to a queue and keep only the last \(200\). After that, search in the trie the current word on the stream. Note that the word on the stream is in the reverse order what matches with the fact that our trie was created with the words reversed. So, the search will find any word in the dictionary that is a prefix of the stream. Time and space complexity is \(O(m)\) where \(m\) is the sum of the length of all words. 

from collections import deque


class StreamChecker:
    def __init__(self, words: List[str]):
        self.stream = deque(maxlen=max(map(len, words)) + 1)
        self.trie = {}
        for w in words:
            node = self.trie
            for c in reversed(w):
                if c not in node:
                    node[c] = {}
                node = node[c]
            node["$"] = True

    def query(self, letter: str) -> bool:
        self.stream.appendleft(letter)
        node = self.trie
        for c in self.stream:
            if "$" in node:
                return True
            if c not in node:
                return False
            node = node[c]
        return "$" in node