Skip to content

Latest commit

 

History

History
401 lines (321 loc) · 15.7 KB

Test.md

File metadata and controls

401 lines (321 loc) · 15.7 KB
up created modified cssclasses
[[Leetcode map.canvas|Leetcode]]
2024-06-25
2024-07-25
wide-page
wide-table

TODO: Currently DV only support loading from csv

  • If I want the [[Leetcode map.canvas|Leetcode dashboard]] to update by category (i.e. in a DP box of dashboard, list all DP problems I've done)
  • need to use separate file (csv) as broker, basically a script that move the table here to csv in a separate file :/

Table

Problem Solution Category Leetcode Difficulty Solved myself? Solved optimal? Note
LC 347. Top K Frequent [[#LC 347. Top K Frequent|link]] Hard Y N
LC 271. Encode Decode String [[#LC 271. Encode Decode Strings|link]] Medium Y Y
LC 212. Word Search II [[#LC 212. Word Search II|link]] Hard N -
LC 70. Climbing Stairs [[#LC 70. Climbing Stairs|link]] [[Dynamic Programming]] Easy Y (well with hint) Y
LC 23. Merge K Sorted List [[#LC 23. Merge K Sorted List|link]] Hard Y Y (kinda)
LC 49. Group Anagrams [[#LC 49. Group Anagram|link]] Medium Y N
LC 39. Combination Sum [[#LC 39. Combination Sum|link]] [[Backtracking]] Medium Y
LC 79. Word Search [[#LC 79. Word Search|link]] Medium Y Y
LC 200. Number of Island [[#LC 200. Number of Island|link]] [[Graph data structure|Graph]]
LC 2685. Count the Number of Complete Components [[#LC 2685. Count the Number of Complete Components|link]] [[Graph data structure|Graph]]
LC 133. Clone Graph link [[Graph data structure|Graph]]
LC 417. Pacific Atlantic Water Flow link [[Graph data structure|Graph]]
fewoij
f
dqwoijoifew
foewijiodqw
dqwoiio

LC 417. Pacific Atlantic Water Flow

LC 133. Clone Graph

LC 2685. Count the Number of Complete Components

LC 200. Number of Island

LC 79. Word Search

O(mn)

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m = len(board)
        n = len(board[0]) if m >= 1 else 0
        def dfs(i, j, z) -> bool:
            if i >= m or i < 0 or j >= n or j < 0:
                return False
            if word[z] == board[i][j]:
                z += 1
                if z == len(word):
                    return True
            else:
                return False
            # search in four directions
            currChar = board[i][j]
            board[i][j] = '*'
            r = dfs(i + 1, j, z)
            r = r or dfs(i - 1, j, z)
            r = r or dfs(i + 1, j, z)
            r = r or dfs(i, j - 1, z)
            r = r or dfs(i, j + 1, z)
            board[i][j] = currChar
            return r
        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True

        return False

LC 39. Combination Sum

class Solution:
    def combinationSum(self, nums: List[int], target: int) -> List[List[int]]:
        result = []
        # set of sets
        lookup = set()
        def getCombination(sums, currSum):
            if currSum < 0:
                return
            if currSum == 0:
                s = str(sorted(sums))
                if s not in lookup:
                    lookup.add(s)
                    result.append(list(sums))
                return
            for n in nums:
                if n <= currSum:
                    sums.append(n)
                    getCombination(sums, currSum - n)
                    sums.pop()
        getCombination([], target)
        return result

K unique element will repeat K! times

LC 49. Group Anagram

My solution

O(NKlog(K)), k = string length, N = n strings

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        l = {}
        for s in strs:
            h = hash(''.join(sorted(s)))
            if h in l:
                l[h].append(s)
            else:
                l[h] = [s]
        res = []
        for _, v in l.items():
            res.append(v)

        return res

Optimal: O(N)

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        ans = defaultdict(list)

        for s in strs:
            count = [0] * 26
            for c in s:
                count[ord(c) - ord("a")] += 1
            ans[tuple(count)].append(s)
        return ans.values()

LC 23. Merge K Sorted List

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
import heapq
class Solution:    
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        h = []
        heapq.heapify(h)
        head = None
        currNode = None

        for n in lists:
            if n:
                tup = (n.val, id(n), n)
                print(tup)
                heapq.heappush(h, tup)

        while len(h) > 0:
            _, _, n = heapq.heappop(h)
            if n.next:
                heapq.heappush(h, (n.next.val, id(n.next), n.next))
            if not head:
                head = n
                currNode = head
            else:
                currNode.next = n
                currNode = n
        
        if currNode:
            currNode.next = None 
            
        return head

LC 70. Climbing Stairs

class Solution {
    private HashMap<Integer, Integer> memo = new HashMap<Integer, Integer>();

    public int climbStairs(int n) {
        if (memo.getOrDefault(n, -1) != -1) {
            return memo.get(n);
        }
        if (n == 0) {
            return 1;
        }
        if (n < 0) {
            return 0;
        }
        int solution = climbStairs(n - 1) + climbStairs(n - 2);
        memo.put(n, solution);
        return solution;
    }
}

LC 212. Word Search II

class TrieNode:
    def __init__(self):
        self.children: Dict[str, TrieNode] = {}
        self.word: Optional[str] = None

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        m = len(board)
        n = len(board[0])
        ans = []
        root = TrieNode()
        
        def insert(word: str) -> None:
            node = root
            for c in word:
                ## commented code is WRONG, because if node children already exists, then this still go ahead
                ## and change the node reference to that newNode created
                ## effectively this doesn't build the Trie correctly
                # newNode = TrieNode()
                # node.children.setdefault(c, newNode)
                # node = newNode
                node = node.children.setdefault(c, TrieNode())
                
            node.word = word

        for w in words:
            insert(w)

        def dfs(i: int, j: int, node: TrieNode) -> None:
            # check out of bound
            if i < 0 or i == len(board) or j < 0 or j == len(board[0]):
                return
            if board[i][j] == "*":
                return
            
            c = board[i][j]
            # add current c to node
            # check if node is complete 
            if c in node.children:
                n = node.children[c]
                if n.word:
                    ans.append(n.word)
                    # "pop" from words to find
                    n.word = None
                # recurse
                board[i][j] = "*"
                dfs(i-1, j, n)
                dfs(i+1, j, n)
                dfs(i, j-1, n)
                dfs(i, j+1, n)
                board[i][j] = c

        for i in range(m):
            for j in range(n):
                dfs(i, j, root)
            
        return ans
# My idea without using Trie and just dfs

class Solution:

# search(prefix, suffix, vistedCoordinates, memoize) -> found

# found when suffix = 0

def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:

# 1. arrange words to prefix (w[0]) and suffix (w[1:])
# 2. for each word prefix, if character at board coordinate = prefix
# add call stack for search
# 3. call search, if true add to result

# search would look adjacent to board, if it's the first character of suffix, recursion with prefix changed

LC 271. Encode Decode Strings

My Solutions:

encode the separator information only in the string

import re
class solution:

    def encode(self, strs: list[str]) -> str:
        if len(strs) == 0:
            return '[]'
        res = []
        for s in strs:
            res.append(s.replace('-', '\-'))
        return '-'.join(res)                    

    def decode(self, s: str) -> list[str]:
        if s == '[]':
            return []
        l = re.split(r'(?<!\\)-', s)
        res = []
        for w in l:
            res.append(re.sub(r'\\-', '-', w))
        return res

His Solution

More elegant than mine, encode separate AND the length information in the string

class Solution:
    
    def encode(self, strs: List[str]) -> str:
        res = ""
        for s in strs:
            res += str(len(s)) + "#" + s
        return res

    def decode(self, s: str) -> List[str]:
        res = []
        i = 0
        
        while i < len(s):
            j = i
            while s[j] != '#':
                j += 1
            length = int(s[i:j])
            i = j + 1
            j = i + length
            res.append(s[i:j])
            i = j
            
        return res

LC 347. Top K Frequent

My solution

Worst case: O(nlogn)

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        numFreq = {}
        for num in nums:
            freq = numFreq.setdefault(num, 0)
            numFreq[num] = freq + 1
        res = [k for k,v in sorted(numFreq.items(), key=lambda item: item[1])]
        return res[len(res) - k:]

His solution

O(n), using array position itself as holder of frequency

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freqNum = [[] for i in range(len(nums) + 1)]
        numFreq = {}
        for num in nums:
            numFreq[num] = numFreq.get(num, 0) + 1
        for num, count in numFreq.items():
            freqNum[count].append(num)
        res = []
        for i in range(len(freqNum) - 1, 0, -1):
            for n in freqNum[i]:
                res.append(n)
                if len(res) == k:
                    return res