[LeetCode] 문자 삭제를 이용하여 사전에서 가장 긴 단어 찾기

문자열과 문자열 사전이 주어지면 주어진 문자열의 일부 문자를 삭제하여 형성 할 수 있는 사전에서 가장 긴 문자열을 찾습니다. 가능한 결과가 두 개 이상인 경우 알파벳 순으로 정렬 시 가장 작은 단어를 반환합니다. 가능한 결과가 없으면 빈 문자열을 반환합니다.

Example 1:

Input: s = "abpcplea", d = ["ale","apple","monkey","plea"]
Output: "apple"

 

Example 2:

Input: s = "abpcplea", d = ["a","b","c"]
Output: "a"

 

Note:

1. 입력의 모든 문자열에는 소문자 만 포함됩니다.
2. 사전의 크기는 1,000을 초과하지 않습니다.
3. 입력에있는 모든 문자열의 길이는 1,000을 초과하지 않습니다.

나의 풀이

class Solution:
    def findLongestWord(self, s: str, d: List[str]) -> str:
        answer = ""
        for word in d:
            i = 0; string = s
            for character in word:
                i = string.find(character)
                if i == -1:
                    break
                string = string[i+1:]
                
            else:
                if len(answer) < len(word):
                    answer = word
                if len(answer) == len(word):
                    answer = min(answer, word)
        return answer

문자열 사전의 단어를 한 문자 씩 순회하며 이전 인덱스를 기점으로 해당 문자의 존재하는 가장 작은 인덱스를 찾습니다. 존재하지 않으면 탈락. 존재하는 경우 현재 단어와 글자 수를 비교하여 더 긴 단어인 경우 answer를 교체, 두 단어의 글자수가 같은 경우 문자열 비교를 통해 더 작은 단어를 answer로 설정합니다.

그리디 알고리즘을 적용하여 해결하였습니다. 시간 제한이 촉박하지 않아서 망정이지, for 문 두 번에 find까지 들어가 굉장히 비효율적인 코드입니다. LeetCode Solution에서는 어떻게 접근하는지 알아보겠습니다.

접근법 1: Brute Force

주어진 문자열에서 하나 이상의 문자를 삭제하여 형성 할 수있는 모든 가능한 문자열 목록을 만듭니다. 이를 위해 문자열 s에서 인덱스 i까지 형성된 문자열 str에 i 번째 문자를 추가하고 제거하여 문자열을 생성하는 재귀 함수 generate (s, str, i, l)를 사용합니다. 따라서 str에 i 번째 문자를 추가하고 generate (s, str + s.charAt (i), i + 1, l)로 자신을 호출합니다. 또한 str에 대한 i 번째 문자를 생략하고 generate (s, str, i + 1, l)로 자신을 호출합니다.

따라서 목록 끝에 l은 s를 사용하여 구성 할 수있는 모든 필수 문자열을 포함합니다. 그런 다음 l로 형성된 문자열을 사용 가능한 사전에서 검색하여 일치하는 항목이 있는지 확인합니다. 일치하는 경우, 일치하는 문자열의 길이를 확인하여 길이를 최대화하고 길이 일치의 경우에도 사전적으로 가장 작은 문자열을 고려합니다.

class Solution:
    def findLongestWord(self, s: str, d: List[str]) -> str:
        self.l = []
        self.generate(s, "", 0)
        max_str = ""
        for string in self.l:
            if string in d:
                if len(string) > len(max_str) or (len(string) == len(max_str) and string < max_str):
                    max_str = string
        return max_str

    def generate(self, s: str, string: str, i: int):
        if i == len(s):
            self.l.append(string)
        else:
            self.generate(s, string + s[i], i+1)
            self.generate(s, string, i+1)

이 경우 시간 복잡도는 O(2^n)으로, generate가 2의 n제곱 번 (n = s의 길이) 호출되고, 공간 복잡도도 마찬가지로 O(2^n)이 되어 시간 초과 혹은 메모리 부족으로 실패하게 됩니다. 아니면 스택이 가득 차 더이상 재귀 함수를 호출할 수 없는 경우도 발생하겠네요.

접근법 2: Iterative Brute Force

재귀 함수를 사용하는 대신 동일한 프로세스를 반복문으로 수행 할 수도 있습니다. 이를 위해 이진수 생성의 개념을 사용합니다.

주어진 문자열 s를 s의 인덱스에 해당하는 이진 표현으로 처리 할 수 ​​있습니다. 문자열과 같은 길이의 이진수를 만들고 해당 인덱스에 글자가 있는 경우에 1로 설정합니다.

총 2 ^ n 개의 이진수가 가능하다는 것을 알고 있습니다. 따라서 우리는 이진 표현의 O에서 2 ^ n까지의 모든 숫자를 직렬 순서로 고려하고 위의 규칙을 사용하여 가능한 모든 문자열을 생성합니다.

아래 그림은 "sea"로부터 생성되는 이진수를 모두 표현한 그림입니다.

 

class Solution:
    def findLongestWord(self, s: str, d: List[str]) -> str:
        l = []
        for i in range(1 << len(s)):
            t = ""
            for j in range(len(s)):
                if ((i >> j) & 1) != 0:
                    t += s[j]    
            l.append(t);
        
        max_str = ""
        for string in l:
            if string in d:
                if len(string) > len(max_str) or (len(string) == len(max_str) and string < max_str):
                    max_str = string
        return max_str
            

이 방법의 문제점은 정수를 사용하고 이진수를 생성하기 위해 시프트 연산을 수행하기 때문에 문자열의 최대 길이는 32 만 가능하다는 것입니다. 또한, 시간 복잡도와 공간 복잡도는 여전히 O(2^n)입니다.

접근법 3: Sorting and Checking Subsequence

주어진 문제의 매칭 조건은 우리가 사전에서 가장 긴 길이를 가진 매칭 문자열을 고려할 필요가 있고, 같은 길이의 경우 사전에 가장 작은 문자열을 고려해야합니다. 검색 프로세스를 용이하게하기 위해 동일한 기준에 따라 주어진 사전의 문자열을 정렬하여 더 유리한 문자열이 정렬 된 사전에서 더 일찍 표시되도록 할 수 있습니다.

이제 s에서 삭제를 수행하는 대신 사전에 제공된 단어 (예 : x)가 사전의 시작부터 시작하여 주어진 문자열 s의 하위 시퀀스인지 직접 확인할 수 있습니다. x가 s의 하위 시퀀스 인 경우 s에서 삭제 작업을 수행하여 x를 얻을 수 있기 때문입니다.

x가 s의 하위 시퀀스이면 x의 모든 문자가 s에 표시됩니다. 이미 d를 길이 순, 알파벳 순으로 정렬 처리했으므로, 이러한 x를 찾으면 검색을 즉시 중지 할 수 있습니다.

class Solution:
    def findLongestWord(self, s: str, d: List[str]) -> str:
        d.sort()
        d.sort(key=lambda x: len(x), reverse=True)
        
        for string in d:
            if self.isSubsequence(string, s):
                return string
        
        return ""
    
    def isSubsequence(self, x: str, y: str) -> bool:
        i = 0; j = 0
        while i < len(y) and j < len(x):
            if x[j] == y[i]:
                j += 1
            i += 1
        return j == len(x)

• 시간 복잡도 : O (n*x*log⁡(n) + n*x). 여기서 n은 d 목록의 문자열 수를 나타내고 x는 평균 문자열 길이를 나타냅니다. 정렬은 O (n log ⁡n)을 사용하고, isSubsequence는 O (x)를 사용하여 문자열이 다른 문자열의 하위 시퀀스인지 여부를 확인합니다.
• 공간 복잡도 : O (log⁡ n). 정렬은 평균적인 경우 O (log ⁡n) 공간을 차지합니다.

접근법 4: Without Sorting

사전 정렬 자체가 추가 연산으로 이어질 수 있으므로 정렬을 건너 뛰고 정렬되지 않은 사전 d에서 x 문자열을 직접 찾을 수 있으므로 x가 s의 하위 시퀀스가됩니다. 이러한 문자열 x가 발견되면 필요한 길이 및 사전식 기준에 따라 지금까지 발견된 다른 일치하는 문자열과 비교합니다. 따라서 d의 모든 문자열을 고려한 후에 필요한 결과를 얻을 수 있습니다.

class Solution:
    def findLongestWord(self, s: str, d: List[str]) -> str:
        max_str = ""
        for string in d:
            if self.isSubsequence(string, s):
                if len(string) > len(max_str) or (len(string) == len(max_str) and string < max_str):
                    max_str = string
            
        return max_str;
    
    def isSubsequence(self, x: str, y: str) -> bool:
        i = 0; j = 0
        while i < len(y) and j < len(x):
            if x[j] == y[i]:
                j += 1
            i += 1
        return j == len(x)

 

• 시간 복잡도 : O (n * x). 모든 문자열에 대해 한 번의 반복이 필요합니다. 여기서 n은 d 목록의 문자열 수를 나타내고 x는 평균 문자열 길이를 나타냅니다.
• 공간 복잡성 : O (x). max_str 변수가 사용됩니다.

각 접근법에 대한 결과는 역순으로 (나의 풀이 ~ 접근법 4)보시면 됩니다. 제 풀이가 제일 빠르네요?? 이해 X