Word Break

문자열 s 가 주어졌을 때 wordDict 안에 있는 문자열로 쪼개는 것이 가능한지 물어보는 문제다.
처음에 브루트포스 방식으로 접근하게 되면 2중 for loop 을 사용해서 모든 문자열을 쪼개고 wordDict 랑 비교하는 방식을 생각해봤다. 이때 Map 을 필수로 사용이 될 것이니 아마 O(n^2) 의 시간으로도 풀 수 있었을 것이다.

그런데 DP 방식으로 생각해보면 더 좋은 방향으로 풀 수 있다. 결국에 wordDict 안에 매칭된 문자가 있다면 그 구간을 기준으로 다음 문자를 비교하는 방식이다. Subproblem 을 생각해봐야 하는 DP 문제에서 좋은 접근 같았다. 그렇기 때문에 첫 인덱스를 기준으로 wordDict 안에 있는 문자와 비교를 했고 매칭되는 구간이 있다면 dp 에 기록을 했다.

DP 배열에 기록하는 방식은 내가 마지막으로 매칭 된 문자가 어디인지 확인하기 위함이고 이런 구간 별로 subproblem 을 만들어야 하는 문제에서 유용하게 사용이 가능할거같다. wordDict 의 길이를 m 이라고 했을 때 시간 복잡도는 O(n*m) 으로 예상된다.

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.length();
        vector<bool> dp(n,false); 

        for(int i = 0; i < n; i++){
            for(string& ss : wordDict){
                if(i < ss.length() - 1) continue; 

                if(i == ss.length() -1 || dp[i - ss.length()]){
                    if(s.substr(i - ss.length() + 1, ss.length()) == ss){
                        dp[i] = true; 
                        break; 
                    }
                }
            }
        }

        return dp[n-1]; 
    }
};