LeetCode 139(Word Break, Python)

1. 문제 링크

• https://leetcode.com/problems/word-break/

Word Break - LeetCode

2. 문제 설명

• 문자열과 사전(단어들이 들어 있는 리스트)이 주어졌을 때, 사전의 단어들을 조합하여(반복 가능) 문자열을 만들 수 있는 지 따져 True, False 반환하기
• 예시) s = "leetcode", wordDict = ["leet", "code"] 이면 “leet” + “code”로 가능하여 True

3. 처음 풀이

• 예시) s = "applepenapple", wordDict = ["apple","pen"]
• s의 첫 글자인 a를 start로 고정하고 end를 순회하며 a, ap, app, appl, apple, applep, …., applepenapple 까지 살펴보며 wordDict에 있는 지 살펴본다. 여기에서 있는 것은 apple 하나이다.
• 그러면 apple까지는 만들 수 있으므로 이제 p는 start로 조사할 후보(candi)이다. p를 start로 고정하고 end를 순회하면 p, pe, pen, …, penapple 중 wordDict에 있는 지 살펴 본다. 여기에서 있는 것은 pen 하나이다.
• 그러면 applepen까지는 만들 수 있으므로 이제 a는 start로 조사할 후보(candi)이다. 마찬가지로 마지막 apple까지 만들 수 있다. 따라서 참.

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # 단어 사전을 집합으으로 변환하여 빠른 검색을 가능하게 함
        wordDict = set(wordDict)
        # 아직 처리하지 않은 부분 문자열의 시작 인덱스를 추적하는 리스트
        candi = [0]
        # 이미 처리한 부분 문자열의 시작 인덱스를 추적하여 중복 처리 방지
        seen = set()
        # 동적 프로그래밍을 위한 2D 배열, 단어 사전을 사용하여 부분 문자열을 나눌 수 있는지 여부 저장
        dp = [[False]*(len(s))] * (len(s))
        
        while candi:
            # 아직 처리하지 않은 부분 문자열의 시작 인덱스를 가져옴
            start = candi.pop(0) 
            if start not in seen:
                seen.add(start)
                # 현재 부분 문자열을 끝까지 순회
                for end in range(start, len(s)):
                    # 현재 부분 문자열이 단어 사전에 있는 단어와 일치하는지 확인
                    if s[start:end + 1] in wordDict:
                        dp[start][end] = True
                        # 다음에 처리할 부분 문자열의 시작 인덱스를 추가
                        if end + 1 not in seen:
                            candi.append(end + 1)

        # 전체 문자열이 단어 사전을 사용하여 나눌 수 있는지 여부를 반환
        return dp[-1][-1]

4. 다른 풀이

• DP를 이용한 풀이, 핵심 아이디어는 비슷하지만 훨씬 깔끔하다.

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
                # Convert wordDict into a set for O(1) lookup
        wordSet = set(wordDict)
        
        # Initialize dp list with false values and set the first value to true
        dp = [False] * (len(s)+1)
        dp[0] = True

        # Iterate over the string
        for i in range(1, len(s)+1):
            # For each position, check all possible words that end at this position
            for j in range(i):
                word=s[j:i]
                if dp[j] and word in wordSet:
                    dp[i] = True
                    break

        # Return if the entire string can be segmented or not
        return dp[len(s)]

---

• 재귀 함수에 메모이제이션을 적용한 풀이
• startswith 이라는 메서드가 있구나.

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        
        def construct(current,wordDict, memo={}):
            if current in memo:
                return memo[current]

            if not current:
                return True

            for word in wordDict:
                if current.startswith(word):
                    new_current = current[len(word):]
                    memo[current] = True
                    if construct(new_current,wordDict,memo):
                        return True

            memo[current] = False
            return False

        return construct(s,wordDict)

5. 배운 점

• 처음에 백트래킹으로 시도했다가 타임 리밋 에러에 걸렸다. 이것 저것 최적화를 시도해보았지만 백트래킹으로 해결하지 못하였다. 백트래킹에 몰입하여 DP를 떠올리지 못하였다. DP… 참 유용하고도 떠올리기 힘든 아이디어..
• 시도했던 백트래킹 풀이가 실패했었는데, 이는 메모이제이션을 적용하지 않았기 때문이다. 마지막 풀이를 보니까 작동 구조는 비슷한데 메모이제이션을 활용하여 빠른 속도를 보여준다.
• str.startswith(prefix[, start[, end]])
  • startswith() 메서드는 문자열이 지정된 접두사로 시작하는지 여부를 검사하는 Python 문자열 메서드
  • prefix: 검사하려는 접두사 문자열입니다.
  • start (옵션): 검사를 시작할 문자열의 인덱스를 지정합니다. 기본값은 0입니다.
  • end (옵션): 검사를 종료할 문자열의 인덱스를 지정합니다. 기본값은 문자열의 길이입니다.
  • startswith() 메서드는 문자열이 지정된 접두사로 시작하면 **True**를 반환하고, 그렇지 않으면 **False**를 반환합니다.

  text = "Hello, world!"
  
  # "Hello"로 시작하는지 확인
  result = text.startswith("Hello")
  print(result)  # 출력: True
  
  # "world"로 시작하는지 확인 (대소문자 구분)
  result = text.startswith("world")
  print(result)  # 출력: False
  
  # 인덱스 7부터 시작하는 "world"로 시작하는지 확인
  result = text.startswith("world", 7)
  print(result)  # 출력: True