[Leetcode 아주 상세한 문제풀이] 139. Word Break - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 139번 문제 Word Break 이다.

우선 문제를 살펴보자.

 

리트코드 139번 문제 Word Break 링크

Word Break - LeetCode

Word Break - LeetCode

 

 

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Example 3:
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

Constraints:
1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s and wordDict[i] consist of only lowercase English letters.
All the strings of wordDict are unique.

 

 

문제 설명

문제에 대해 간략히 살펴보자.

문자열 s와 특정 문자열로 이루어진 wordDict라는 dictionary가 주어진다. 이때 문자열 s를 쪼갰을 때 그 쪼개진 단어들이 wordDict안에 있는 문자에 들어있는지 확인하는 문제다.

문제 예시 1번에서 보는 것처럼 문자열 s는 "leetcode" 그리고 wordDict은 "leet", "code"로 주어졌을 때 주어진 문자열 s는 "leet"와 "code" 로 쪼개질 수 있고 이는 wordDict 안에 존재하므로 true를 리턴하면 된다.

문제를 이해하는데 어렵지 않기 때문에 곧바로 문제를 풀어보도록 하자.

 

 

문제 접근법

문자열 s가 주어졌을때 우리는 어디를 끊어야  wordDict에 있는 문자열에 해당하는지 판단할 수 없기 때문에,

주어진 문자열을 처음부터 하나하나 탐색해나가야 한다.

예를 들어 문제에서 주어진 예시 1번을 가지고 설명해보자.

이 예시에서 주어진 문자열은 "leetcode"이고 wordDict은 "leet"와 "code"이다.

우리는 문자열 leetcode를 왼쪽부터 하나씩 탐색해나갈 것인데,

이때 해당 자리에서 끊었을 때 wordDict안에 끊어진 문자가 존재하는지 판단하기 위해

True와 False로 표현하는 boolean array를 하나 만들어 줄 것이다.

즉, 해당 자리에서 boolean array값이 T라면 해당 자리에서 끊었을 때 끊어진 문자가 wordDict안에 존재한다는 뜻이다.

우선 초기값으로 모든 자리에 Flase값을 설정해 주는데,

Empty string은 언제나 쪼갤수 있기 때문에 boolean array의 첫번째 인덱스는 True로 지정해 준다.

 

그 후 우리는 문자열 s를 왼쪽에서 오른쪽으로 하나씩 탐색해 나갈 예정인데,

이때 중요한 점은 해당구간의 모든 subsequence를 탐색해 봐야 한다는 것이다.

예를 들어 아래와 같이 'e'를 탐색하고 있다고 하자.

 

이 경우 'e'가 마지막에 오는 모든 subsequence, 즉

s[0] 부터 s[2]: 'lee'

s[1] 부터 s[2]: 'ee'

s[2] 부터 s[2]: 'e'

를 모두 탐색하여 이것이 wordDict안에 있는지 확인해 봐야한다. 

 

 

문자열을 끊었을 때

이제 문자열을 끊었을 때 그 문자가 wordDict안에 있을 때를 살펴보자.

위와 같이 문자열을 탐색해 나가다가 't'를 탐색하는 경우를 살펴보자.

위에서 설명한 것 처럼 이 경우도 't'가 마지막에 오는 subsequence를 모두 살펴봐야 한다.

그 subsequence 중 하나가'leet'가 되고 이는 wordDict에 포함된다.

이때 중요한것은 subsequence 탐색시 가장 앞쪽에 위치한 문자 (= "l") 앞쪽에 위치한 boolean array가 True인지 확인해 봐야 한다.

Boolean array가 true라는 것은 거기서 문자열 s를 끊을 수 있다는 뜻이기 때문이다.

따라서 이 경우 "leet"라는 subsequence가 탐색되었을 때

i) "leet"가 wordDict에 포함되고

ii) Subsequence 가장 앞에 위치한 문자 ("l") 앞 boolean array값이 true

이기 때문에 탐색하고 있는 문자열 "t"의 boolean array를 True로 업데이트 한다.

 

이해를 돕기위해 문자열의 마지막 문자 "e"를 탐색하는 경우를 살펴보자. 

이 경우 boolean array의 첫번째 값을 왜 True로 초기화 해야하는지 더욱 명확해진다.

문자열 s에서 'e'를 탐색할 때 그 subsequene 중 "code"를 탐색할 때

i) "code"가 wordDict에 포함되고

ii) Subsequence 가장 앞에 위치한 문자 ("c") 앞boolean array값이 true

이기 때문에 탐색하고 있는 문자열 "e"의 boolean array를 True로 업데이트 한다.

여기서 보는 것처럼 boolean array가 True 값을 갖는 다는 것은 그 자리에서 문자열을 끊었을 때

끊어진 문자열이 wordDict안에 포함된다는 것이다.

위의 경우에서 보는 것처럼 "t"에서 한 번 끊은 후 그 이후에 위치한 문자 "e"를 탐색할 때

"e"로 끈나는 subsequence 중 wordDict에 들어갈 수 있는 문자인지 판단하는데 중요한기준이 된다.

 

 

문제 풀이

코드로 한 번 살펴보자.

우선 문자열 s와 문자열 dictionary를 입력받을 함수를 정의한다 (line 1)

그리고 좀 더 빠른 탐색을 위해 set 함수를 이용한다 (line 3)

참고로 set 함수는 중복되는 것들을 없애 탐색 속도를 증가시킨다.

앞서 설명한 boolean array를 만들어 주는데 (line 6)

그 크기는 앞서 설명한 empty string을 고려하여 입력된 문자열 s보다 하나 크게 만들어 준다.

그리고 첫번째 인덱스 값은 True로 나머지는 False로 초기화를 해준다 (line 6-7)

Double for loop를 이용해 문자열을 하나하나 탐색하는데 (line 9-10)

이때 두 가지 조건 (line 11)

i) 탐색하고 있는 문자가 마지막에 위치한 subsequence가 wordDict에 존재하는지

ii) 그 subsequence 바로 앞에 위치한 boolean array가 True인지 (= 끊을 수 있는 지점인지)

두 가지 조건이 부합한다면 해당 boolean array 값을 True로 업데이트 해준다 (line 12) 

그리고 최종적으로 boolean array에서 마지막 값을 리턴 해주는데,

그 이유는 boolean array의 마지막 값이 True가 아니라는 뜻은

문자열 앞쪽에서 제대로 끊어지지 않아 문자열 마지막 값으로 위 조건을 만족할 수 없는 문자가 남기 때문이다.

 

 

문제 풀이 코드

def wordBreak(s, wordDict):
    # Create a set for faster lookup
    word_set = set(wordDict)
    
    # Initialize a boolean array to track if a substring can be segmented
    dp = [False] * (len(s) + 1)
    dp[0] = True  # An empty string can always be segmented
 
    for i in range(1, len(s) + 1):
        for j in range(i):
            print("i= ", i)
            print("j= ", j)
            print(s[j:i])
            if dp[j] and s[j:i] in word_set:
                
                dp[i] = True
                print('true dp= ', dp)
                break
            print("dp =", dp)
            print("-----------------------")
    return dp[len(s)]
 
# Test cases
s1 = "leetcode"
wordDict1 = ["leet", "code"]
print(wordBreak(s1, wordDict1))  # Output: True
 
#s2 = "applepenapple"
#wordDict2 = ["apple", "pen"]
#print(wordBreak(s2, wordDict2))  # Output: True
 
#s3 = "catsandog"
#wordDict3 = ["cats", "dog", "sand", "and", "cat"]
#print(wordBreak(s3, wordDict3))  # Output: False