The idea is the following:
d is an array that contains booleans
d[i] is True if there is a word in the dictionary that ends at ith index of s AND d is also True at the beginning of the word
s = "leetcode"
words = ["leet", "code"]
d is True because there is "leet" in the dictionary that ends at 3rd index of "leetcode"
d is True because there is "code" in the dictionary that ends at the 7th index of "leetcode" AND d is True
The result is the last index of d.
def word_break(s, words): d = [False] * len(s) for i in range(len(s)): for w in words: if w == s[i-len(w)+1:i+1] and (d[i-len(w)] or i-len(w) == -1): d[i] = True return d[-1]
I think your answer is well suited for small dictionaries. What if they use real vocabulary dictionary which may contain million words. Wont the running time will be more for your solution.
@attila.magyar.144 This solution is beautiful. I hardly use this word to describe code. But this one surely deserves it :)
@attila-magyar-144 Beautiful solution. Could I ask what is i-len(w)==-1 for?
@zxzhijia It means the dictionary word is the head of string.
@zxzhijia Does that mean the following example s = "leetcode" ; dict = ["leet", 'codes']?
when we are trying to search to 'codes', it will trigger the condition "i - len('codes') = -1"?
Beautiful Solution indeed, I rewrote the code with slight modification for corner case :
Now no need to check
def wordBreak(self, s, wordDict): n = len(s) dp = [False for i in range(n+1)]//*Changed* dp = True for i in range(1,n+1): for w in wordDict: if dp[i-len(w)] and s[i-len(w):i]==w://*Changed* dp[i]=True return dp[-1]
@priyaranjan No dictionary contains a million words. https://en.oxforddictionaries.com/explore/how-many-words-are-there-in-the-english-language
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.