[ leetcode 문제풀이 ] Word Break

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

Word Break - LeetCode

(Word Break 문제는 위 링크에서 풀어보실 수 있습니다.)

< Word Break 문제 설명 >

Word Break 문제는 다음과 같다.

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

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

 

주어진 문자열 s와 문자열 사전 wordDict에 대해 s가 wordDict의 단어들의 합으로 나타낼 수 있으면 true를 출력하여라.(단 wordDict의 단어를 여러 번 사용할 수 있음)

다음 세 가지 출력 예시가 주어졌다.

주어진 제한 조건은 1 ≤ s.length ≤ 300, 1 ≤ wordDict.length ≤ 1000, 1 ≤ wordDict[i].length ≤ 20, s와 wordDict[i]는 소문자로만 구성되어 있음, wordDict에는 중복된 문자열이 존재하지 않는다는 것이다.

 

---

< Word Break 문제 접근 >

문자열 s를 wordDict의 단어들의 합으로 나타낼 수 있는가를 탐색하기 위해 가장 쉽게 할 수 있는 방법은 s의 앞에서부터 wordDict의 원소(단어)와 1:1비교를 한 후 wordDict의 단어가 s에 포함된다면 이 중복되는 부분을 지우는 것이다. 이 과정을 재귀적으로 반복해 만약 s의 모든 문자가 지워진다면 true값을 리턴하게 되는 것이다.

이렇게 아직 지워지지 않은 s의 부분 remain_s를 매개변수로 하는 WordBreak(string remain_s)이라는 함수를 완전 탐색 알고리즘으로 생각해낼 수 있다.

하지만 동적 계획법을 적용하기엔 조금 아쉽다. 입력이 문자열이기에 메모이제이션을 적용하기에 불편하다. 따라서 부분 문제를 다음과 같이 정의해보기로 하자. 정수 start를 입력으로 받는 WordBreak(int start)를 s[start:]와 wordDict 간의 word break 문제에 대한 해답이라 하는 것이다. 문자열을 입력으로 받는 함수와 본질적으로 하는 역할은 같으나 int를 입력으로 받았기에 메모이제이션 하기에도 용이해졌다.

메모이제이션까지 적용한 함수를 코드로 나타내면 아래와 같다. (Cpp사용)

int cache[300];			// memoization을 위한 배열(s 길의 최댓값 만큼의 크기를 가짐)
std::fill_n(cache, 300, -1);		// 할당된 값이 없음을 의미하는 -1

bool WordBreak(int start, string s, vector<string>& wordDict){		// s[start:]에 대한 WordBreak
    if(start == s.length())
        return true;			// 조건을 만족하는 경우 s에 wordbreak가 완료되었으므로 true
    int& ret=cache[start];
    if(ret != -1)				
        return (bool)ret;		// memoization 값을 bool형태로 출력
        
    ret=0;		// 종료 조건이 line 5밖에 없으므로 이외의 모든 경우를 표현하기 위해 0(false)로 초기화
    for(int wdorder=0;wdorder<wordDict.size();wdorder++){	// wordDict의 모든 원소에 대한 탐색
        bool isMatch = true;
        for(int pos=0;pos<wordDict[wdorder].length();pos++)
            if(s[start+pos] != wordDict[wdorder][pos] || start + wordDict[wdorder].length() > s.length()){
                isMatch = false;
                break;
            }
        if(isMatch)			// s 앞부분부터 wordDict[i]가 포함되어 있다면 
            ret = (int)WordBreak(start+wordDict[wdorder].size(), s, wordDict);		
        if(ret == 1)			// 한번이라도 wordBreak가 성립하면 탐색 종료
            break;
    }
    return (bool)ret;
}

>> run WordBreak(0, s, wordDict)

 bool type의 출력을 메모이제이션과 함께 다루려고 하다보니 메모이제이션을 위한 cache 배열을 잘 다루기가 꽤나 힘들었다.