[LeetCode] 139 - Word Break

문제

• 링크: https://leetcode.com/problems/word-break
• 난이도: Medium
• 태그: 배열, 해시테이블, 문자열, 다이내믹 프로그래밍, 메모이제이션
• 결과: Time: 0 ms (100.00%), Space: 11.34 MB (75.27%)

풀이

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        this->s = s;
        return solve(0, wordDict);
    }

    bool solve(int start, vector<string>& wordDict)
    {
        if (memo.contains(start))
        {
            return memo[start];
        }

        if (start == s.size())
        {
            return true;
        }

        for (auto& str : wordDict)
        {
            if (s.substr(start, str.size()) == str)
            {
                if (solve(start + str.size(), wordDict))
                {
                    memo[start] = true;
                    return true;
                }
            }
        }

        memo[start] = false;
        return false;
    }

private:
    string s;
    unordered_map<int, bool> memo;
};

DP로 풀었다. wordDict를 순회해서 해당 단어가 prefix가 맞으면, 그 길이만큼 substr해서 재귀 호출을 진행한다.

배운 점과 후기

풀이의 기초 틀은 잡아뒀는데, 끝내 제대로 풀지 못하고 AI에게 힌트를 받아가면서 풀었다. DP 특훈, 이제 미룰 수 없다! 바로 시작해야겠다.

이 포스트는 달레 스터디(5주차)에서 진행한 Blind 75 문제집 풀이의 일부입니다.