Word Break | Leetcode

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

---

Solution: Maintain an array of booleans (canBreak) to mark whether the particular position can be broken up into dictionary words. For example, "canBreak[i] = true" means that the string from characters 0 to (i - 1) can break into dictionary words.

Iterate through the string from first to last position. For each position i, go through all the dictionary words to check whether the word can contribute to the break. Let word be the dictionary word, and endIndex = i + word.length(). Check if "canBreak[i] = true" and "word.equals(s.substring(i, endIndex)) == true". If both conditions were true, then set canBreak[endIndex] = true. If endIndex == s.length(), then we know the whole word can be broken into dictionary words, so return true.

public class Solution {
    public boolean wordBreak(String s, Set<String> wordDict) {
        boolean[] canBreak = new boolean[s.length()];
        
        for (int i = 0; i < s.length(); i++) {
            if (i > 0 && !canBreak[i]) continue;
            
            for (String word: wordDict) {
                int endIndex = i + word.length();
                if (endIndex > s.length()) continue;
                if (endIndex < s.length() && canBreak[endIndex]) continue;
                
                if (s.substring(i, endIndex).equals(word)) {
                    if (endIndex == s.length()) return true;
                    canBreak[endIndex] = true;
                }
            }
        }
        
        return false;
    }
}