pjaehyun의 개발일지

문제

https://leetcode.com/problems/lexicographically-smallest-equivalent-string/description/

You are given two strings of the same length s1 and s2 and a string baseStr.

We say s1[i] and s2[i] are equivalent characters.

• For example, if s1 = "abc" and s2 = "cde", then we have 'a' == 'c', 'b' == 'd', and 'c' == 'e'.

Equivalent characters follow the usual rules of any equivalence relation:

• Reflexivity: 'a' == 'a'.
• Symmetry: 'a' == 'b' implies 'b' == 'a'.
• Transitivity: 'a' == 'b' and 'b' == 'c' implies 'a' == 'c'.

For example, given the equivalency information from s1 = "abc" and s2 = "cde", "acd" and "aab" are equivalent strings of baseStr = "eed", and "aab" is the lexicographically smallest equivalent string of baseStr.

Return the lexicographically smallest equivalent string of baseStr by using the equivalency information from s1 and s2.

Example 1:

Example 2:

Example 3:

Constraints:

• 1 <= s1.length, s2.length, baseStr <= 1000
• s1.length == s2.length
• s1, s2, and baseStr consist of lowercase English letters.

문제풀이 코드

class Solution:
    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
        UF = {}

        def find(x):
            if x not in UF:
                UF[x] = x
            
            if x != UF[x]:
                print(x, UF[x])
                UF[x] = find(UF[x])
            return UF[x]
                

        def union(x, y):
            # 두 값의 루트값을 탐색
            rootX = find(x)
            rootY = find(y)
			
            # 두 루트값 중 더 작은 값을 루트노드로 초기화한다
            if rootX > rootY:
                UF[rootX] = rootY
            else:
                UF[rootY] = rootX
        
        for i in range(len(s1)):
            union(s1[i], s2[i])
        
        answer = ""
        for s in baseStr:
            answer += find(s)
        return answer

풀이방식: 서로 연결된 알파벳들은 연결된 알파벳 중 가장 작은 알파벳으로 루트값을 가져가야 하기 때문에 Union-Find 알고리즘 사용

1. 기본적인 Union-Find 알고리즘을 구현한다

  - union: 두 값의 루트 값을 찾아 둘 중 더 작은 값을 가지는 루트값으로 루트노드를 바꿔준다.

  - find: 재귀 함수를 통해 현재 값의 루트값을 찾는다.

2. union 함수에 s1[i]와 s2[i]를 파라미터로 넣어 호출한다.(s1[i]와 s2[i]는 같은 집합)

3. 반복문이 종료되면 UF는 같은 집합끼리 묶여 그 집합내에 가장 작은 값을 루트노드로 가지게 된다.

4. baseStr의 문자들과 연결되는 값을 find함수를 통해 찾아온다.

문제

https://leetcode.com/problems/longest-path-with-different-adjacent-characters/

You are given a tree (i.e. a connected, undirected graph that has no cycles) rooted at node 0 consisting of n nodes numbered from 0 to n - 1. The tree is represented by a 0-indexed array parent of size n, where parent[i] is the parent of node i. Since node 0 is the root, parent[0] == -1.

You are also given a string s of length n, where s[i] is the character assigned to node i.

Return the length of the longest path in the tree such that no pair of adjacent nodes on the path have the same character assigned to them.

Example 1:

Input: parent = [-1,0,0,1,1,2], s = "abacbe"
Output: 3
Explanation: The longest path where each two adjacent nodes have different characters in the tree is the path: 0 -> 1 -> 3. The length of this path is 3, so 3 is returned.
It can be proven that there is no longer path that satisfies the conditions. 

Example 2:

Input: parent = [-1,0,0,0], s = "aabc"
Output: 3
Explanation: The longest path where each two adjacent nodes have different characters is the path: 2 -> 0 -> 3. The length of this path is 3, so 3 is returned.

Constraints:

• n == parent.length == s.length
• 1 <= n <= 105
• 0 <= parent[i] <= n - 1 for all i >= 1
• parent[0] == -1
• parent represents a valid tree.
• s consists of only lowercase English letters.

문제풀이 코드

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        n = len(parent)

        tree = defaultdict(list)
        for end, start in enumerate(parent):
            tree[start].append(end)
        
        answer = 1
        def dfs(node):
            nonlocal answer
            res = 1
            for child in tree[node]:
                l = dfs(child)
                if s[node] != s[child]:
                    answer = max(answer, res + l)
                    res = max(res, l+1)
            return res
        dfs(0)
        return answer

1. 트리형태의 그래프를 만들어 준다. ex) {0:[1,2], 1:[3,4], 2:[5]}

2. 최소값은 자기 노드 하나이기 때문에 answer를 1로 초기화

3. 그래프를 탐색하기 위한 dfs 함수를 만들어준다.

  - 현재 연결된 노드의 최솟값은 1이기 때문에 현재 연결된 노드들을 1로 선언

  - 현재 노드의 자식노드들을 탐색한다.

  - 노드를 탐색할 때 l = dfs(child)를 통해 자식노드가 그 하위노드와 연결된 최대값을 가져온다.

  - 현재 알파벳과 자식노드의 알파벳이 다를 때 answer와 res를 초기화해준다.

    -> answer = max(answer, res+l): res+l 은 현재의 노드부터 이전에 연결된 노드들의 갯수로 초기화해준다.

    -> res = max(res, l+1): l+1은 이전 연결된 노드에 현재 노드를 연결한 값으로 초기화해준다.

4. dfs가 종료되면 answer에는 최대로 연결된 노드의 개수가 들어가있기 때문에 answer를 반환한다.

문제

https://leetcode.com/problems/word-search/

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

Example 2:

문제풀이 코드

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        row, col = len(board), len(board[0])
        visited = [[False] * col for _ in range(row)]
        def dfs(x,y,s):
            if s == len(word):
                return True
            if x < 0 or x > row-1 or y < 0 or y > col-1 or word[s] != board[x][y] or visited[x][y]:
                return False
            visited[x][y] = True
            res = (dfs(x+1,y, s+1) or dfs(x,y+1, s+1) or
                   dfs(x-1,y, s+1) or dfs(x,y-1, s+1))
            visited[x][y] = False
            return res
        for i in range(row):
            for j in range(col):
                if dfs(i,j,0):
                    return True
        return False

주어진 알파벳들로 주어진 단어를 만들 수 있는지 체크하는 것이기 때문에 dfs를 이용하여 문제풀이

1. 좌,우,위.아래를 탐색해야 되기 때문에 현재 x,y가 조건에 맞는지 체크한다.

2. 그리고 가장 핵심이 되는 현재 연결된 단어가 word의 부분인지 확인하기 위해 현재 알파벳과, word의 s번째 순서의 알파벳이 같은지 비교한다.

3. 조건을 만족했을 때, 모든 방향으로 dfs를 호출한다.
4. 호출된 dfs중 하나라도 True가 존재하면 res는 True가 된다.

5. 배열을 전부 돌면서 dfs(i,j,0)이 True일 때 True를 반환하고

6. 반복문이 정상적으로 종료된다면 False를 반환한다.

문제

https://leetcode.com/problems/perfect-squares/

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Example 1:

Example 2:

문제풀이 코드

# Dp 풀이 방식
class Solution:
    def numSquares(self, n: int) -> int:
        dp = [inf for _ in range(10001)]
        dp[0] = 0
        ps = []
        
        i = 1
        while i*i <= n:
            ps.append(i*i)
            i += 1
        
        for i in range(1, n + 1):
            for s in ps:
                if i < s:
                    break
                dp[i] = min(dp[i], dp[i-s] + 1)  
        return dp[n]

# Bfs 풀이 방식
class Solution:
    def numSquares(self, n: int) -> int:
        if n < 2:
            return n

        perfect_square = []
        i = 1
        while i * i <= n:
            perfect_square.append(i*i)
            i += 1
        
        check = {n}
        count = 0
        while check:
            count += 1
            temp = set()
            for num in check:
                for square in perfect_square:
                    if num == square:
                        return count
                    if num < square:
                        break
                    temp.add(num - square)
            check = temp
        return count

다이나믹 프로그래밍 풀이

1. 0은 만들 수 있는 수가 없고, 1은 1로 만들 수 있고, 2는 1+1로 만들 수 있고, 3은 1+1+1로 만들 수 있고, 4는 4로 만들 수 있다.

2. 식으로 변형하면 dp[0] = 0, dp[1] = 1, dp[2] = 2, dp[3] = 3, dp[4] = 1이 된다.

3. 예를 들어 구해야되는 수가 7이면, 7 = 4 + 3(1 + 1 + 1)이 되기 때문에 dp[7-4] + 1이 되게 된다.

4. 이를통해 점화식을 구하면 dp[i] = min(dp[i], dp[i-제곱수] + 1)가 된다.

5. n 보다 작은 모든 제곱수를 담은 리스트를 만들고 1 ~ n까지 반복문을 돌면서

6. s가 i보다 작을때만 dp[i]를 초기화 해준다.(i = 3인데 제곱수가 4가나오면 계산할 수 없음)

7. 반복문이 종료되면 dp[n]을 반환한다.

BFS 풀이

1. 다이나믹 프로그래밍과 동일하게 n보다 작은 모든 제곱수를 리스트에 담아준다.

2. 체크할 수를 딕셔너리 형태로 저장(이 후 연산후 중복된 값이 들어가지 않도록하기위함)

3. 반복문을 돌때마다 카운트를 1씩 증가시켜준다.

4. check에 있는 수에 모든 제곱수를 빼준다.

5. 연산된 숫자들이 담긴 집합을 check에 담아준다.

6. 반복하면서 check에 제곱수가 들어가있다면 현재 count를 반환한다.

문제

https://leetcode.com/problems/word-search-ii/description/

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example 1:

Example 2:

문제풀이 코드

# 문자열 탐색 자료구조
class Trie:
    def __init__(self):
        self.trie = {}
        
    def insert(self, word):
        current = self.trie
        for w in word:
            if w not in current:
                current[w] = {}
            current = current[w]
        current['#'] = '#'
        
    def remove(self, word):
        current = self.trie
        nodes = []
        for w in word:
            if w not in current:
                return False
            current = current[w]
            nodes.append((current, w))
        
        if '#' in current:
            remove = '#'
            for node, w in nodes[::-1]:
                if remove == '#' or len(node[remove]) == 0: del(node[remove])
                remove = w

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
        row, col = len(board), len(board[0])
        result = set()
        root = Trie()
        visited = [[False] * col for _ in range(row)]
        
        for w in words:
            root.insert(w)
		
        # 백트래킹
        def dfs(x, y, word, trie):
            if x < 0 or x >= row or y < 0 or y >= col or visited[x][y] or board[x][y] not in trie:
                return
            visited[x][y] = True
            word = word + board[x][y]
            trie = trie[board[x][y]]
            if '#' in trie:
                result.add(word)
                root.remove(word)
            for i in range(4):
                xx, yy = x + dx[i], y + dy[i]
                dfs(xx, yy, word, trie)
            visited[x][y] = False

        for i in range(row):
            for j in range(col):
                dfs(i, j, "", root.trie)
        return list(result)

백트래킹 + 문자열탐색 Trie자료구조

처음 문제를 접근할 때 Trie자료구조를 사용하지않고 모든 문자열을 비교하여 시간초과가 나옴..

다른 접근법을 참조하니 Trie자료구조를 이용하여 더 빠르게 문자열을 탐색할 수 있어 풀이 변경

1. 트라이 자료구조 구현(insert, remove)

2. 백트래킹을 사용하여 모든 알파벳 탐색

3. 일반적인 백트래킹 기법에서 조건을 하나 추가하여 탐색 진행 -> 현재 trie에 '#'이 들어있다면 현재 word는 존재하는 단어로 결과에 추가해주고 탐색한 단어는 삭제해줌으로 중복 탐색하는 경우를 제거

4. 모든 재귀호출이 종료되면 결과를 list로 반환한다.

문제

https://leetcode.com/problems/reverse-vowels-of-a-string/

Given a string s, reverse only all the vowels in the string and return it.

The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in both lower and upper cases, more than once.

문자열 s안에 있는 모든 모음들을 뒤집어서 반환해라, 모음은 대문자도 포함

Example 1:

Example 2:

문제풀이 코드

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = {'a','e','i','o','u','A','E','I','O','U'}
        s = list(s)
        i, j = 0, len(s) - 1

        while i < j:
            # s[i]가 모음 집합에 들어가있고, s[j]는 안들어가있다면 j -= 1 해준다
            if s[i] in vowels and s[j] not in vowels:
                j -= 1
                continue
            # s[j]가 모음 집합에 들어가있고, s[i]는 안들어가있다면 i += 1 해준다    
            elif s[i] not in vowels and s[j] in vowels:
                i += 1
                continue
            # s[i]가 모음 집합에 들어가있고, s[j]도 들어가있다면 s[i]와 s[j]의 위치를 바꾼다
            elif s[i] in vowels and s[j] in vowels:
                s[i], s[j] = s[j], s[i]
            i += 1
            j -= 1
        return ''.join(s)

투포인터로 문제 접근

1. i = 0, j = len(s) -1 로 초기화한다

2. i번째 문자가 모음이고 j번째 문자는 모음이 아닐 때 j = j - 1을 해준다.

3. j번째 문자가 모음이고 i번째 문자는 모음이 아닐 때 i = i + 1을 해준다.

4. i번째 문자가 모음이고 j번째 문자도 모음일 때 s[i]와 s[j]의 자리를 바꿔주고 i = i + 1, j = j - 1을 해준다

5. 반복문이 종료되면 문자열로 변환하여 반환한다.

문제

https://leetcode.com/problems/longest-palindrome-by-concatenating-two-letter-words/

ou are given an array of strings words. Each element of words consists of two lowercase English letters.

Create the longest possible palindrome by selecting some elements from words and concatenating them in any order. Each element can be selected at most once.

Return the length of the longest palindrome that you can create. If it is impossible to create any palindrome, return 0.

A palindrome is a string that reads the same forward and backward.

Example 1:

Example 2:

Example 3:

문제풀이 코드

class Solution:
    def longestPalindrome(self, words: List[str]) -> int:
        counter = Counter(words)
        result = mid = 0
        string = ""
        for word in counter.keys():
            # "aa", "bb" 같은 문자열
            if word[0] == word[1]:
                # "aa"의 갯수가 짝수면 갯수, 홀수면 -1 을 더해준다
                result += counter[word] if counter[word] % 2 == 0 else counter[word] - 1
                # 모든 앞뒤가 같은 단어들 중 홀수가 하나라도있으면 mid = 1
                mid |= counter[word] % 2
            # "cl", "lc" 같은 단어 일 때 
            elif word[::-1] in counter:
                # 앞뒤로 이어붙일 수 있는 단어는 둘개의 단어를 카운트 했을 때 더 갯수가 더 작은 쪽으로 더해준다
                # Ex) ["lc", "lc", "lc", "cl", "cl"] 일 때,
                # "lclcclcl"은 되지만 "lclclcclcl"은 성립하지 않는다.
                result += min(counter[word], counter[word[::-1]])
        # 모든 단어는 2글자로 되어있으니 * 2를 해준다
        return (result+mid)*2

1. 모든 단어들을 Counter함수를 통해 갯수를 샌다.

2. 단어는 "aa" 앞뒤가 같은단어 또는 "lc" 앞뒤가 다른 단어가 올 수 있다.

3. 앞뒤가 같은 단어일 때는 짝수로 나누어지면 해당 단어의 갯수를 result에 더해주고 홀수일때는 -1을 해서 짝수만큼 더해준다

4. 같은단어가 홀수개 있을 때 mid = 1

5. 앞뒤가 다른 단어일 때는 현재 단어의 갯수와 뒤집었을 때 단어의 갯수 중 더 작은 값을 result에 더해준다

6. 모든 단어는 2글자이기 때문에 (result + mid) * 2를 반환한다

문제

https://leetcode.com/problems/minimum-genetic-mutation/

A gene string can be represented by an 8-character long string, with choices from 'A', 'C', 'G', and 'T'.

Suppose we need to investigate a mutation from a gene string startGene to a gene string endGene where one mutation is defined as one single character changed in the gene string.

• For example, "AACCGGTT" --> "AACCGGTA" is one mutation.

There is also a gene bank bank that records all the valid gene mutations. A gene must be in bank to make it a valid gene string.

Given the two gene strings startGene and endGene and the gene bank bank, return the minimum number of mutations needed to mutate from startGene to endGene. If there is no such a mutation, return -1.

Note that the starting point is assumed to be valid, so it might not be included in the bank.

시작 유전자인 startGene과 마지막 유전자인 endGend, 변경할 수 있는 모든 돌연변이가 저장되어있는 bank가 주어질 때, startGene에서 endGend까지 가기위한 최소 돌연변이의 수를 반환해라

- 유전자는 한번에 하나씩 변경 가능하다 ex) "AACCGGTT" --> "AACCGGTA" 

- 변경할 수 있는 돌연변이가 없다면 -1을 반환한다

Example 1:

Example 2:

문제풀이 코드

class Solution:
    def minMutation(self, start: str, end: str, bank: List[str]) -> int:
        
        # 현재 유전자에서 알파벳 하나만 변경했을 때 이웃한 유전자로 변경할 수 있는지 체크
        def checkOneMutation(str1, str2):
            return sum([1 for i in range(len(str1)) if str1[i] != str2[i]]) == 1
            
        visited = set()
        visited.add(start)
        dq = deque([[start, 0]])
        
        while dq:
            current, mutation = dq.popleft()
            
            if current == end:
                return mutation
            
            for neighbor in bank:
                if checkOneMutation(current, neighbor) and neighbor not in visited:
                    visited.add(neighbor)
                    dq.append([neighbor, mutation + 1])
        return -1

1시간 문제를 풀어보고 해결방법이 생각나지않아 풀이방법 참고(BFS를 이용하여 풀이)

1. checkOneMutation함수를 만들어서 현재 유전자와 이웃한 돌연변이 유전자간에 다른 문자가 1개일땐 True 아니면 False

2. 중복방문을 방지하기 위해서 visited를 초기화해준다

3. current가 end와 같으면 유전자변경이 끝나서 현재 변경 횟수를 반환한다.

4. bank안에 모든 돌연변이를 탐색한다

5. 돌연변이가 checkOneMutation이 True이고 방문한적이 없다면 방문처리를 해주고 dq에 추가해준다.

6. 모든 유전자 변경을 했지만 end까지 도달하지 못한경우 -1을 반환한다