leetCode解题报告之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".

分析：

一开始看到这个题目，我的第一反应是要递归，但是之后感觉递归的做法估计没办法通过，然后就开始想，之后看到别人的思路之后，感觉其实还挺容易的。

解题思路：

一个字符串S，它的长度为N，如果S能够被“字典集合”（dict）中的单词拼接而成，那么所要满足的条件为：

F(0, N) = F(0, i) && F(i, j) && F(j, N);

这样子，如果我们想知道某个子串是否可由Dict中的几个单词拼接而成就可以用这样的方式得到结果（满足条件为True, 不满足条件为False）存入到一个boolean数组的对应位置上，这样子，最后boolean数组的最后一位就是F(0, N)的值，为True表示这个字符串S可由Dict中的单词拼接，否则不行！

话不多说，上AC代码！！

package cn.xym.leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution {
        /**
	 * 方法二：
	 */
	public boolean wordBreak2(String s, Set<String> dict){
		int len = s.length();
		boolean[] arrays = new boolean[len+1];
		arrays[0] = true;
		for (int i = 1; i <= len; ++i){
			for (int j = 0; j < i; ++j){
				if (arrays[j] && dict.contains(s.substring(j, i))){
					// f(n) = f(0,i) + f(i,j) + f(j,n)
					arrays[i] = true;
					break;
				}
			}
		}
		return arrays[len];
	}
	/*
	 * 方法一：
	 * */
	public boolean wordBreak1(String s, Set<String> dict) {
		boolean flag = false;
		int strLen = s.length();
        List<Integer> list = new ArrayList<Integer>();
        for (int i=strLen-1; i>=0; --i){
        	String endSubStr = s.substring(i);
        	if (dict.contains(endSubStr)){
        		list.add(i);
        	}else{
        		for(Integer n : list){
        			if (dict.contains(s.substring(i,n))){
        				list.add(i);
        				break;
        			}
        		}
        	}
        }
        if (list.isEmpty()){
        	flag = false;
        }else{
        	Integer n = list.get(list.size() - 1);
        	flag = n == 0 ? true : false;
        }
        return flag;
	}
	
	
	public static void main(String[] args) {
		String s = "leetcode";
		Set<String> dict = new HashSet<String>();
		dict.add("leet");
		dict.add("code");
		Solution solution = new Solution();
		System.out.println(solution.wordBreak2(s, dict));
	}
}

leetCode解题报告之Word Break,布布扣,bubuko.com

leetCode解题报告之Word Break

原文：http://blog.csdn.net/ljphhj/article/details/21643391