[LeetCode] 140. Word Break II

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

leetcode - Word Break II

문제 유형 : 문자열 처리, 다이나믹 프로그래밍

문제 난이도 : Hard

 

문제

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

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

 

문자열 s와 wordDict라는 문자열 딕셔너리가 주어진다.

문자열 s에 공백을 넣어서 wordDict에 있는 단어들로 만들 수 있는 모든 문장을 반환하시오.

순서는 상환없습니다.

같은 단어가 여러 번 사용될 수 있습니다.

 

풀이

dp[i] = i번째 이후의 suffix문자열들의 문장화시킨 집합이라고 생각해보자.

만약 s = "...catdog", wordDict = ["cat", "dog", ...]이면,

dp[n-3] = {"dog ", ...}이다..

dp[n-6] = {"cat dog ", ...}이다.

(n = s의길이)

문자열의 끝부분부터 보면서, 기본 케이스dp[n] = {""}을 만들어놓고, 현재 인덱스에서 붙일 수 있는 단어가 있는지 찾아보고,

있다면, 각 단어에 대해서 연결해주면 된다.

 

위의 경우에서, i = n-6일때, "cat"을 붙일 수 있다면, 

dp[i] = "cat" + " " +  [dp[i+3(cat의 길이)]에 있는 문자열들]을 해주면 되겠다.

dp[0]에는 0번 인덱스부터의 suffix문자열, 즉 원본 문자열을 문장화시킨 집합이 들어있다.

 

코드

C++

class Solution {
private:
    int n;
public:
    bool check(string &s, string &word, int idx, int wordlen) {
        int i = 0;
        while(i < wordlen) {
            if(i + idx >= n || s[i + idx] != word[i]) return false;
            i++;
        }

        return true;
    }
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        // dp[idx] = suffix with s[idx] ~ s[s.size()-1].
        // ex) s = "~~dog", word Dict = ["dog", ...] => dp[n-3] = {"dog ", ...}.
        
        n = s.size();
        vector<vector<string>> dp(n+1, vector<string>());
        dp[n] = {""};
        for(int i = n-1; i >= 0; i--) {
            for(string &word : wordDict) {
                int wordlen = word.size();
                if(check(s, word, i, wordlen)) {
                    for(string suffix : dp[i + wordlen]) {
                        dp[i].push_back(word + " " + suffix);
                    }
                }
            }
        }

        // remove trailing space.
        for(string &sentence : dp[0]) {
            sentence.pop_back();
        }
        return dp[0];
    }
};