✉️문제
https://leetcode.com/problems/word-break/description/
Word Break - LeetCode
Can you solve this real interview question? Word Break - Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Note that the same word in the dictionary may
leetcode.com
📝 접근
기본적인 아이디어는 wordDict안에 들어있는 word의 길이 만큼 문자열 s를 substring 한 뒤에 비교한다.
이때, 문자열 s의 알파벳이 모두 분리가 되는지 확인하기 위해 1차원 배열을 사용한다.
🗝 문제풀이
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
boolean[] dy = new boolean[n + 1];
dy[n] = true;
for(int i = n - 1; i >= 0; i--) {
for(String word : wordDict) {
if(i + word.length() <= n && word.equals(s.substring(i, i + word.length()))) {
dy[i] = dy[i + word.length()];
}
if(dy[i]) break;
}
}
return dy[0];
}
}