(DP, Medium) Word Break

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

DP왜이렇게 어렵냐.. 고민하다 솔루션 참고

아이디어는 s 길이 + 1만큼의 boolean dp[] 배열을 만들고 해당 인덱스까지(== 문자열에서 해당 포인트까지) 접근 가능한지 여부를 true/false 세팅해둔 뒤

최종적으로 dp[s.length()]하면 풀 길이 문자열이 만들어질지 여부를 알 수 있게 됨

핵심은 두 가지를 확인해야 한다.

1. 현재 지점(i)에서 wordDict가 가진 최대 길이 문자열 사이(i~j)를 substring으로 잘라낸 것이 wordDict에서 찾아지냐? 즉, 사전에 있는 단어로 만들어진 문자열이냐?
2. 현재 지점(i)에서 wordDict가 가진 최대 길이 문자열만큼 떨어진 dp 값이 true냐? 즉, 여기까지는 만들 수 있었냐?

1번은 당연히 사전으로 만들 수 있는 문자열인지 확인하는 것이고
2번은 1번으로 만들어진 단어가 누적되며 문자열을 만들어 나가는 것이기 때문에 직전이 false면 체크 대상이 아니게 된다.

그러므로 둘은 AND 조건이여야 하며 해당하는 경우 dp[i]에는 다시 true를 세팅해준다.

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        
        int n = s.length();

        boolean[] dp = new boolean[n + 1];
        dp[0] = true;

        // 사전에서 가장 길이가 긴 단어의 길이
        int maxWordLength = 0;
        for (String word : wordDict) {
            maxWordLength = Math.max(maxWordLength, word.length());
        }

        for (int i=1; i<=n; i++) {
            for (int j=i; j>=Math.max(0, i - maxWordLength - 1); j--) {
                if (dp[j] && wordDict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[n];
    }
}