classSolution: # @param s, a string # @param wordDict, a set<string> # @return a boolean defwordBreak(self, s, wordDict): ifnot s: returnTrue ifnot wordDict: returnFalse
max_word_len = max([len(w) for w in wordDict]) can_break = [True] for i in xrange(len(s)): can_break.append(False) for j in xrange(i, -1, -1): # optimize for too long interval if i - j + 1 > max_word_len: break if can_break[j] and s[j:i + 1] in wordDict: can_break[i + 1] = True break return can_break[-1]
classSolution { public: boolwordBreak(string s, unordered_set<string>& wordDict){ if (s.empty()) returntrue; if (wordDict.empty()) returnfalse;
// get the max word length of wordDict int max_word_len = 0; for (unordered_set<string>::iterator it = wordDict.begin(); it != wordDict.end(); ++it) {
max_word_len = max(max_word_len, (*it).size()); }
vector<bool> can_break(s.size() + 1, false); can_break[0] = true; for (int i = 1; i <= s.size(); ++i) { for (int j = i - 1; j >= 0; --j) { // optimize for too long interval if (i - j > max_word_len) break;
if (can_break[j] && wordDict.find(s.substr(j, i - j)) != wordDict.end()) {
publicclassSolution { publicbooleanwordBreak(String s, Set<String> wordDict) { if (s == null || s.length() == 0) returntrue; if (wordDict == null || wordDict.isEmpty()) returnfalse;
// get the max word length of wordDict intmax_word_len=0; for (String word : wordDict) { max_word_len = Math.max(max_word_len, word.length()); }
boolean[] can_break = newboolean[s.length() + 1]; can_break[0] = true; for (inti=1; i <= s.length(); i++) { for (intj= i - 1; j >= 0; j--) { // optimize for too long interval if (i - j > max_word_len) break;