[LeetCode] 139. Word Break

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

Word Break - LeetCode

문제 유형 : 동적계획법, 문자열처리

문제 난이도 : Medium

 

문제

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated 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라는 단어 사전에 있는 단어만으로 문자열을 나눌 수 있는지 구분하시오.

단, 단어는 재사용 가능하다.

 

풀이

빠른 wordDict 탐색을 위해서 unordered_set을 이용한다.

부울 값의 dp 테이블을 (n+1)개 만든다. s의 각 인덱스까지별로 부분 문자열이 wordDict의 단어로 분할 가능한지 저장하는 배열이다.

dp[0]은 빈 문자열을 가정하므로, true를 저장시킨다.

 

중첩 반복문을 만들어서 s[0]부터 s[i]까지 가능한지 에 대해 dp 테이블을 완성한다.

 

dp[n+1]은 문자열 s의 가능 여부를 담는다.

 

코드(C++)

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        
        unordered_set<string> dict(wordDict.begin(), wordDict.end());
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;

        for (int i = 1; i <= s.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (dp[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[s.size()];
    }
};