[leetcode 139] Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

wordDict에 있는 단어들로 주어진 s를 빠짐없이 분리할 수 있는가

 

Note:

• The same word in the dictionary may be reused multiple times in the segmentation.
• You may assume the dictionary does not contain duplicate words.

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

 

접근:

현재 위치에 대해 모든 문자열을 확인한다.

현재 위치가 모든 문자열의 길이보다 작다면 dp[i] = false

문자열의 길이와 동일한 것이 있다면 일치여부를 확인한다.

문자열의 길이보다 크다면 현재위치에서 문자열의 길이만큼 뺀 위치가 true인지 확인하고 일치여부를 확인한다.

dp[i] = dp[i-문자열길이] && (i-문자열 +1부터 i까지가 문자열과 일치하는지 여부)

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        
        int len = s.length();
        int dicLen = wordDict.size();
        
        bool dp[len];
        memset(dp, false, sizeof(dp));
        
        for(int i=0; i<len; i++){
            
            for(int j=0; j<dicLen; j++){
                string cmp = wordDict[j];
                
                if(i > cmp.length() -1){
                    int startIdx = i - cmp.length();
                    string sub = s.substr(startIdx+1, cmp.length());
                    
                    if(dp[startIdx] && !cmp.compare(sub)){
                        dp[i] = true;
                        break;
                    }
                    
                }else if(i == cmp.length()-1){
                    string sub = s.substr(0, i+1);
                    
                    if(!cmp.compare(sub)){
                        dp[i] = true;
                        break;
                    }
                }
                
            }
        }
        
        return dp[len-1];
    }
};