每天一道算法题（五）Leetcode – Word Break Java

本篇文章主要介绍了"每天一道算法题（五）Leetcode – Word Break Java"，主要涉及到break,word方面的内容，对于Javajrs看球网直播吧_低调看直播体育app软件下载_低调看体育直播感兴趣的同学可以参考一下： Problem: Given a string s and a dictionary of words dict, determine if s can be...

Problem:
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”.
即：是否可以把一个字符串拆分成单词字典dict的一个或多个词

---

因为这两天接触了动态规划，所以我准备试试能不能用dp算法去解出这道题。
思路：

1. • 建一个数组来存储状态dp，空串或前面是dict里单词的字符的index所在的状态是true
2. 定义一个初始状态，dp[0] = true，即空串为true
3. 根据dict里面的单词字符创去和以从字符串第一个字符开始的字符串比较，如果相等，给字符串中的这个单词的下一个字符的dp[nextChar] = true;
4. 根据状态进行一些判断

---

代码：

publicboolean wordBreak(String str ,Set dict {

        boolean[] dp = newboolean[str.length()+1];
        dp[0] = true;//set first to be true, why?//Because we need initial statefor (int i = 0; i < str.length(); i++) {
            //should continue from match positionif (!dp[i]) 
                continue; 

            for (String word : dict) {
                int len = word.length();
                int end = i + len;

                if (end > str.length()) 
                    continue;

                if (dp[end]) 
                    continue;

                if (str.substring(i , end).equals(word)) {
                    dp[end] = true;
                }
            }
        }
        return dp[str.length()];
    }
    @Test
    publicvoid testWordBreak(){
        String str = "leetcode";
        String[] strs = {"leet", "code"};  
        Set dict = new HashSet(Arrays.asList(strs));  
        System.out.println(wordBreak(str, dict));
    }

').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('

').text(i)); }; $numbering.fadeIn(1700); }); });

以上就介绍了每天一道算法题（五）Leetcode – Word Break Java，包括了break,word方面的内容，希望对Javajrs看球网直播吧_低调看直播体育app软件下载_低调看体育直播有兴趣的朋友有所帮助。

本文网址链接：http://www.codes51.com/article/detail_746063.html