【Leetcode】Word Break

題目鏈接：https://leetcode.com/problems/word-break/

題目：

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".

思路：

res[i] = res[j]&wordDict.contains(s.subString(j,i))；

從0~i的字符串能用單詞表示 取決于 是不是存在從0~j的字符串能用單詞表示，且從j~i是1個單詞。j<i

算法：

1. public boolean wordBreak(String s, Set<String> wordDict) {  
2.         boolean res[] = new boolean[s.length() + 1];// 表示到i為止的子串能否用單詞表示  
3.         res[0] = true;  
4.         for (int i = 0; i <= s.length(); i++) {  
5.             for (int j = 0; j < i; j++) {  
6.                 if (res[j] && wordDict.contains(s.substring(j, i))) {  
7.                     res[i] = true;  
8.                     break;  
9.                 }  
10.             }  
11.         }  
12.         return res[s.length()];  
13.     }  

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈