23.03.03 Today’s Leetcode

28. Find the Index of the First Occurrence in a String (medium)

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        for i in range(len(haystack) - len(needle) + 1):
            if haystack[i:i + len(needle)] == needle:
                return i
        return -1

202. Happy Number (easy)

class Solution:
    def isHappy(self, n: int) -> bool:
        visited = set()
        def dfs(k):
            if k == 1:
                return True
            if k in visited:
                return False
            visited.add(k)
            num = 0
            while k > 0:
                num += (k % 10) ** 2
                k = k // 10
            # print(num)
            return dfs(num)
        
        return dfs(n)

204. Count Primes (medium)

Sieve of Eratosthenes

class Solution:
# @param {integer} n
# @return {integer}
    def countPrimes(self, n):
        if n < 3:
            return 0
        primes = [True] * n
        primes[0] = primes[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if primes[i]:
                primes[i * i: n: i] = [False] * len(primes[i * i: n: i])
        return sum(primes)

207. Course Schedule (medium)

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        tree = defaultdict(list)
        for a, b in prerequisites:
            tree[a].append(b)

        dp = [False] * numCourses        
        def dfs(cur, visited):
            if dp[cur]:
                return True
            if cur in visited:
                return False
            visited.add(cur)
            for node in tree[cur]:
                if not dfs(node, visited):
                    return False
            visited.remove(cur)
            dp[cur] = True
            return True
        
        for i in range(numCourses):
           if not dfs(i, set()):
                return False 
        return True

208. Implement Trie (Prefix Tree) (medium)

Trie : link 한줄로 요약하자면, Tree 형태를 띄는 데이터구조로 문자열의 prefix 연산을 쉽게 하기위해서 사용함.

class TrieNode:
     # Initialize your data structure here.
    def __init__(self):
        self.word = False
        self.children = {}
    
class Trie:
    
    def __init__(self):
        self.root = TrieNode()
    
    # @param {string} word
    # @return {void}
    # Inserts a word into the trie.
    def insert(self, word):
        node = self.root
        for i in word:
            if i not in node.children:
                node.children[i] = TrieNode()
            node = node.children[i]
        node.word = True
    
    # @param {string} word
    # @return {boolean}
    # Returns if the word is in the trie.
    def search(self, word):
        node = self.root
        for i in word:
            if i not in node.children:
                return False
            node = node.children[i]
        return node.word
    
    # @param {string} prefix
    # @return {boolean}
    # Returns if there is any word in the trie
    # that starts with the given prefix.
    def startsWith(self, prefix):
        node = self.root
        for i in prefix:
            if i not in node.children:
                return False
            node = node.children[i]
        return True
            
    
    # Your Trie object will be instantiated and called as such:
    # trie = Trie()
    # trie.insert("somestring")
    # trie.search("key")

46. Permutations (medium)

class Solution:
    def permute(self, nums) -> List[List[int]]:
        res = []
        
        def dfs(path, not_used):
            if not not_used:
                res.append(path[:])
            # print(path, not_used)
            for i in not_used:
                path.append(i)
                temp = set(not_used)
                temp.remove(i)
                dfs(path, temp)
                path.pop()

        a, b = [], set(nums)
        dfs(a, b)
        return res

class Solution:
    # DFS
    def permute(self, nums):
        res = []
        self.dfs(nums, [], res)
        return res
        
    def dfs(self, nums, path, res):
        if not nums:
            res.append(path)
            # return # backtracking
        for i in range(len(nums)):
            self.dfs(nums[:i] + nums[i+1:], path + [nums[i]], res)

77. Combinations (medium)

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        def dfs(path, start):
            if len(path) == k:
                res.append(path[:])
            for i in range(start + 1, n + 1):
                path.append(i)
                dfs(path, i)
                path.pop()
        
        dfs([], 0)
        return res

784. Letter Case Permutation (medium)

class Solution:
    def letterCasePermutation(self, s: str) -> List[str]:
        res = []

        def dfs(start, text):
            check = True
            for i in range(start, len(text)):
                if text[i].isalpha():
                    check = False
                    dfs(i + 1, text[:i] + text[i].upper() + text[i + 1:])
                    dfs(i + 1, text[:i] + text[i].lower() + text[i + 1:])
                    return
            if check:
                res.append(text)
            
        dfs(0, s)
        return res