[Dynamic Programming][Medium] 139. Word Break

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

 

 

Q. 주어진 string s를 wordDict 안의 단어로 자른다고 했을때, 정확하게 잘라지는지 여부를 반환하라. 

 이때, word Dict안의 단어는 과정에서 여러번 사용 될 수 있다. 

 

Solution. 

 특정 위치에서 캐릭터를 하나 비교하면서 이동한다. 

 이 과정에서,

 현재 맞춰가는 word Dict의 단어가 없다면, 

 모든 word dict를 대상으로 그 첫 캐릭터가 있는지를 찾는다.

 현재 맞춰가는 word dict의 단어가 있다면, 계속 진행하면서 캐릭터가 같거나 아니거나 두 가지만 존재한다. 

 

 로직과 캐시에 맞춰 코드를 써 본다.

bool wordBreak_dp(vector<string>& wordDict, int idxDict, string& s, int idx, int wIdx, map<string, bool>& vCache)
{
    if (idx >= s.size())
        return wIdx==0;

    string key = to_string(idx) + "-" + to_string(idxDict) + "-" + to_string(wIdx);
    if(vCache.find(key) != vCache.end())
        return vCache[key];

    bool ret = false;
    if(idxDict >= 0)
    {
        if(s[idx] == wordDict[idxDict][wIdx])
        {
            if (wIdx == wordDict[idxDict].size() - 1)
                ret = wordBreak_dp(wordDict, -1, s, idx + 1, 0, vCache);
            else
                ret = wordBreak_dp(wordDict, idxDict, s, idx + 1, wIdx + 1, vCache);
        }
    }
    else 
    {
        for (int k = 0; k < wordDict.size(); ++k)
        {
            if (wIdx<wordDict[k].size() && s[idx]==wordDict[k][wIdx])
            {
                if (wIdx == wordDict[k].size() - 1)
                    ret = wordBreak_dp(wordDict, -1, s, idx + 1, 0, vCache);
                else
                    ret = wordBreak_dp(wordDict, k, s, idx + 1, wIdx + 1, vCache);
            }
            if(ret)    break;
        }
    }

    vCache[key] = ret ? 1 : 0;
    return ret;
}

bool wordBreak(string s, vector<string>& wordDict) 
{
    map<string, bool> vCache;
    return wordBreak_dp(wordDict, -1, s, 0, 0, vCache);
}

 

 

생각보다 조금 복잡해 졌고 결과도 중간 이하이다.

다시 생각해 본다. 

 

 

이번에는 캐릭터를 일일이 체크하는 방식이 아닌, 단어 전체를 검사하고 건너뛰는 방식을 사용한다. 

 

bool wordBreak_dp(unordered_map<string, bool>& mapCache, string s, vector<string>& wordDict)
{
    if(s.empty())   return true;

    if(mapCache.find(s) != mapCache.end())
        return mapCache[s];

    bool bRet = false;
    for (int q = 0; q < wordDict.size(); ++q)
    {
        if (s.size() < wordDict[q].size())
            continue;

        string subStr = s.substr(0, wordDict[q].size());
        if (subStr == wordDict[q])
        {
            if (wordBreak_dp(mapCache, s.substr(subStr.size()), wordDict))
            {
                bRet = true;
                break;
            }
        }
    }
    return mapCache[s] = bRet;
}

bool wordBreak(string s, vector<string>& wordDict) 
{
    unordered_map<string, bool> mapCache;
    return wordBreak_dp(mapCache, s, wordDict);
}

 

 

훨씬 간결한 코드와 함께 더 나은 결과를 얻었다.