[LeetCode] WordBreak C++ 풀이

https://leetcode.com/problems/word-break/description/?envType=problem-list-v2&envId=array

Word Break - LeetCode

 

Source Code

class Solution {
public:
    set<string> words;
    int dp[301];

    bool recursive(string s, int start) {
        if (dp[start] != -1) return dp[start];

        if (start >= s.length()) {
            return true;
        }

        bool breakable = false;
        for(int j = start; j < s.length(); j++) {
            string sub = s.substr(start, j - start + 1);
            if(words.find(sub) != words.end()) {
                if(recursive(s, j + 1)) {
                    breakable = true;
                }
            }
        }
        return dp[start] = breakable;
    }

    bool wordBreak(string s, vector<string>& wordDict) {
        for(int i = 0; i< 300; i++) {
            dp[i] = -1;
        }
        for(string word: wordDict) {
            words.insert(word);
        }
        return recursive(s, 0);
    }
};

 

Recursive + Dynamic Programming 기법으로 풀었다. 

s.substr(start, j) 가 wordDict에 존재하는 지 확인하고, 존재한다면 다음 스택에 start = j + 1를 파라미터로 하여 다음 substring을 검증하는 방식이다. 

wordDict에 존재하는 즉시 순회를 멈추고 다음 스택으로 넘어가는 것이 아니라, 순회를 계속 이어가면서 다른 wordDict에 포함된 단어가 있는 지 확인하였다. 

그 이유는, catsandog 에서 start = 0일때 cat과 cats 두가지 경우의 수가 발견될 수 있기 때문이다. 하지만 가장 짧은 단어를 찾은 이후 멈춘다면 cats를 발견할 수 없고, wordDict에 sand가 없다고 가정했을 때 cats/and 조합을 발견할수 없기 때문이다.

 

시간복잡도

recursive(start) 는 DP 에 의해서 start위치마다 한번씩 계산된다.

1. recursive(start)의 호출 횟수 = O(N)

2. for(int j = start; j < n; j++) = O(N)

3. substr()에 의해 문자열 복사 = O(N)

최종적으로 O(N^3)의 시간복잡도

 

공간복잡도

1. dp 배열 = O(N)

2. 재귀호출에 의한 스택 사용 = O(N)

3. set<string> words = O(M) 여기서 M  은 wordDict에 있는 총 문자의 개수

최종적으로 O(N + M) 의 공간복잡도

 

https://www.geeksforgeeks.org/dsa/word-break-problem-dp-32/

Word Break - GeeksforGeeks

 

다른 풀이 참고