LeetCode (C/C++) 139. Word Break

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

---

풀이 및 코드

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {

        for(int i = 0; i < wordDict.size(); i++) {

            while (1){
                int idx = s.find(wordDict[i]);

                if (idx == string::npos)
                    break;

                s.erase(idx, wordDict[i].length());
                cout << s << "\n";
            }
        }
        if (s.length())
            return false;
        return true;
    }
};

 

wordDict의 원소를 앞에서부터 확인하면서 주어진 문자열에 존재한다면 해당 부분을 지우는 방식으로 풀었다.

s : ["cars"]
wordDict : ["cars", "ca", "rs"]

 

하지만 이 풀이는 위와 같이 뒤의 문자열들로 조합이 가능한 경우를 고려하지 못 해 틀렸다.

 

---

 

다른 사람들의 풀이를 보니 dp + 메모이제이션으로 풀어서 해당 방법으로 풀어서 맞췄다.

class Solution {
public:

    bool wordBreak(string s, vector<string>& wordDict) {
        bool dp[301] = {false, };
        dp[0] = true;
        
        for(int i = 0; i < s.length(); i++) {
            if (!dp[i])
                continue;
            for (int j = 0; j < wordDict.size(); j++) {
                string word = wordDict[j];
                string cmpStr = s.substr(i, word.length());

                if (cmpStr.compare(word) == 0)
                    dp[i + word.length()] = true;
            }
        }
        if (dp[s.length()])
            return true;
        return false;
    }  
};

 

여러 풀이가 존재했고, 그 중 이해했던 풀이로 코드를 작성했다.

문자열 s의 인덱스를 하나씩 옮겨가며 해당 위치에서 wordDict에 일치하는 단어가 있는지 확인하고, 있다면 dp 배열을 true로 바꿔준다.

 

아래에는 해당 코드의 작동 방식을 위의 테스트케이스로 예를 들어 설명했다.

ex.

 

s : "cars"
word : "car", "ca", "rs"

 

dp = {1, 0, 0, 0, 0}

 

----------------------------------

 

i = 0

dp[0]  =true & "car", "ca" 존재 -> dp[3], dp[2] true

dp = {1, 0, 1, 1, 0}

 

----------------------------------

 

i = 1

dp[1] = false

dp = {1, 0, 1, 1, 0}

 

----------------------------------

 

i = 2

dp[2] = true & "rs" 존재 -> dp[4] = true

dp = {1, 0, 1, 1, 1}

 

----------------------------------

 

i = 3

dp[3] = true , "s" 존재 x

 

----------------------------------

 

dp[s.length()] = true

ans : true

 

 

풀이 참고 자료

https://seohyun0120.tistory.com/entry/LeetCode-Word-Break-%ED%92%80%EC%9D%B4-python-%ED%8C%8C%EC%9D%B4%EC%8D%AC

[LeetCode] Word Break 풀이 - (python 파이썬)