[LeetCode] 139. Word Break

😎풀이

해당 문제를 풀이하는 과정은 다음과 같다.

1. dp를 통해 해당 인덱스의 문자열 까지 분할이 가능한 단어인지를 판별한다.
2. 2중 반복을 통해 순회하며 이전까지의 분할 가능 여부와 현재까지의 분할 가능여부를 판단한다.
3. 최종적으로 문자열의 끝까지 분할이 가능한지 확인한다.

function wordBreak(s: string, wordDict: string[]): boolean {
    // dp[i]는 문자열 s의 처음부터 i번째 위치까지가 wordDict의 단어들로 분할 가능한지를 나타냄
    const dp: boolean[] = new Array(s.length + 1).fill(false);
    
    // 빈 문자열은 항상 분할 가능하므로 true로 초기화
    dp[0] = true;
    
    // 문자열의 각 위치에 대해 반복
    for (let i = 1; i <= s.length; i++) {
        // 현재 위치(i)에서 이전의 모든 위치(j)를 검사
        for (let j = 0; j < i; j++) {
            // 이전 위치(j)까지 분할이 가능하고
            // j부터 i까지의 부분 문자열이 사전에 있다면
            // 현재 위치(i)까지의 분할도 가능
            if (dp[j] && wordDict.includes(s.slice(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    
    // 전체 문자열의 분할 가능 여부 반환
    return dp[s.length];
}