23.04.18 Today’s Leetcode

1768. Merge Strings Alternately (easy)

class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        i = j = 0
        n1, n2 = len(word1), len(word2)
        res = ''
        while True:
            if i < n1:
                res += word1[i]
                i += 1
            if j < n2:
                res += word2[j]
                j += 1
            if i == n1 and j == n2:
                break
        return res

2645. Minimum Additions to Make Valid String (medium)

처음에는 max(counter.value) 값의 3배에 len(word) 을 빼면 될 줄 알았으나 실패.
이전 문자열보다 큰 경우, 예를 들어서 ‘ab’ 와 ‘bc’ 같은 경우를 제외하여 카운팅 한 결과 통과.

class Solution:
    def addMinimum(self, word: str) -> int:
        k, prev = 0, 'z'
        for c in word:
            k += c <= prev
            prev = c
        return k * 3 - len(word)

707. Design Linked List (medium)

class Node:
    def __init__(self, val=0, next_=None):
        self.val = val
        self.next = next_

class MyLinkedList:

    def __init__(self):
        self.base = Node(0)
        self.tail = self.base
        

    def get(self, index: int) -> int:
        cur = self.base
        for i in range(index + 1):
            if not cur:
                return -1
            cur = cur.next
        if cur:
            return cur.val
        return -1

    def addAtHead(self, val: int) -> None:
        temp = self.base.next 
        self.base.next = Node(val)
        self.base.next.next = temp
        

    def addAtTail(self, val: int) -> None:
        cur = self.base
        prev = self.base
        while cur:
            prev = cur
            cur = cur.next
        prev.next = Node(val)
       

    def addAtIndex(self, index: int, val: int) -> None:
        cur = self.base
        for i in range(index):
            if not cur:
                return None
            cur = cur.next
        if not cur:
            return None
        temp = cur.next
        cur.next = Node(val)
        cur.next.next = temp

    def deleteAtIndex(self, index: int) -> None:
        cur = self.base
        for i in range(index):
            cur = cur.next
        if cur and cur.next:
            cur.next = cur.next.next


# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

820. Short Encoding of Words (medium)

class P:
    def __init__(self):
        self.d = {}
    
    def add(self, word):
        n = len(word)
        i = n - 1
        cur_d = self.d
        while i >= 0:
            if word[i] not in cur_d:
                cur_d[word[i]] = {}
            cur_d = cur_d[word[i]]
            i -= 1
        cur_d[0] = 1

    def count(self):
        
        def dfs(cur, count):
            if len(cur.keys()) == 1 and 0 in cur:
                print(count)
                return count
            temp = 0
            for key in cur.keys():
                if key == 0:
                    continue
                temp += dfs(cur[key], count + 1)
            return temp
        
        return dfs(self.d, 1)


class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        d = defaultdict(list)
        p = P()
        for word in words:
            p.add(word) 

        return p.count()

less verbal solution

몬가 몬가 신기한 python 문법들.

class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        trie = (d := lambda: defaultdict(d))()  # multi-level collections.defaultdict
        for word in words:
            curr = trie
            for i in range(len(word)):
                curr = curr[word[~i]]
        return (dfs := lambda node, curr: sum(dfs(adj, curr+1) for adj in node.values()) if node else curr)(trie, 1)

1957. Delete Characters to Make Fancy String (easy)

class Solution:
    def makeFancyString(self, s: str) -> str:
        i = 0
        n = len(s)
        res = ''
        while i < n:
            j = i + 1
            while j < n and s[j] == s[i]:
                j += 1
            count = j - i
            if count >= 2:
                res += s[i] * 2
            else:
                res += s[i]
            i = j
        return res