Leetcode - 139. Word Break

문제

주어진 문자열이 wordDict에 포함된 문자열로만 구성되어있는지 파악하라.

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

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

해결 아이디어

문자열을 두부분으로 나누고 왼쪽이 hash table에 있는지 파악, 그리고 오른쪽은 recursive 함수가 결과를 리턴한다. 이것을 재귀적으로 반복.

"cat"     "sandog"
 ^^^       ^^^^^^
 true      recursion
          "sand"      "og"
           ^^^^        ^^
           true        recursion -> false


"cats"    "andog"
 ^^^^      ^^^^^
 true      recursion
          "and"      "dog"
           ^^^        ^^^
           true       recursion -> true

brute force

class Solution {
    unordered_set<string> w_table;
    int ssize;
    
    bool recur(string s, int start) {
        if (start == ssize)
            return true;
        
        for (int last = start + 1; last <= ssize; last++) {
            if (w_table.find(s.substr(start, last - start)) == w_table.end())
                continue;
            if (recur(s, last))
                return true;
        }
        return false;
    }
    
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        ssize = s.length();
        for (auto a: wordDict)
            w_table.insert(a);
        return recur(s, 0);
    }
};

brute force + memoization

class Solution {
    unordered_set<string> w_table;
    int ssize;
    vector<int> mem;
    
    bool recur(string s, int start) {
        if (start == ssize)
            return true;
        if (mem[start] != -1)
            return mem[start];
        
        for (int last = start + 1; last <= ssize; last++) {
            if (w_table.find(s.substr(start, last - start)) == w_table.end())
                continue;
            if (recur(s, last)) {
                mem[start] = true; // idx is start (not last)
                return mem[start];
            }
        }
        mem[start] = false;
        return mem[start];
    }
    
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        ssize = s.length();
        mem.assign(ssize, -1);
        for (auto a: wordDict)
            w_table.insert(a);
        return recur(s, 0);
    }
};