LeetCode题目链接:139. Word Break

2017/04/01 Algorithm

tips: 动态规划典型题目

LeetCode题目链接:139. 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”.

分析

首先,容易想到,该问题是可以分解的,我们用WordBreak(s)表示s是否可以分词,那么WordBreak(“leetcode”)可以分解为

WordBreak("eetcode") && "l" in dict or
WordBreak("etcode") && "le" in dict or
WordBreak("tcode") && "lee" in dict or
...
WordBreak("") && "leetcode" in dict

因此容易想到如下算法

算法1 WordBreak(s,dict)
	 //判断字符串s是否可以分词
	 //输入:s,待判断字符串;dict,分词词典
	 //输出:true,s可以分词;false:s不可以分词

	 ret <- false
	 for i <- 1 to s.length do
	 	  if s[1..i] in dict && WordBreak(s[i+1..s.length],dict)
			 ret = true;
	
	 return ret 分析算法复杂度:易有

T(n) = T(n - 1) + T (n - 2) + ...T(1)

容易得到算法复杂度是O(2n)。继续分析算法1,容易发现存在大量重复的子问题,如WordBreak(“code”)在WordBreak(“eetcode”),WordBreak(“etcode”),WordBreak(“tcode”),WordBreak(“code”)中被重复计算,因此可以采用记忆化搜索的方法,将计算过得结果保存在数组里,发现重复问题时,直接返回结果即可,避免重复计算。同时我们发现,子问题的规模其实是在不断缩小的,直至字符串为空。因此,我们可以采用动态规划的方法,先解决空字符串问题,然后依次解决更大规模问题,直至原问题得到解。记忆化搜索和动态规划联系可以看这里.因此有如下算法:

算法2 WordBreak(s,dict)
	 //判断字符串s是否可以分词
	 //输入:s,待判断字符串;dict,分词词典
	 //输出:true,s可以分词;false:s不可以分词

	res[0..s.length] <- false 	//res[i]表示长度为i的单词是否可以分词

	res[0] <- true
	for i <- 1 to s.length do  //依次解决子问题
		for j <- 1 to i do
			if s[j..i] in dict && res[j]
				res[i] = true

	return res[s.length]

分析算法复杂度显然是O(n2)的。

tips:对于一个问题,我们首先判断该问题是否可分,可分的情况又分为两种,一种是DC类型的,像快速排序,直接分为两个不相干的子问题,问题规模也明显变小(快速排序子问题规模为原问题1/2)。另一种是step by step的(可以搜索中科院计算所卜东波老师算法路线图)。如本题。后者往往存在重复的子问题,这个时候,就可以尝试使用动态规划去解决。

源代码

import java.util.Set;

public class Solution {
    public boolean wordBreak(String s, Set<String> wordDict) {
    	if(s == null || s.length() == 0){
    		return true;
    	}
    	
    	int maxLen = 0;
    	for(String ite : wordDict){
    	    maxLen = maxLen > ite.length() ? maxLen : ite.length();
    	}
    	
    	boolean[] res = new boolean[s.length() + 1];
    	
    	res[0] = true;
    	
    	for(int i = 1; i < res.length; i++){
    		for(int j = Math.max(0,i - maxLen); j < i; j++){
    			if(res[j] && wordDict.contains(s.substring(j, i))){
    				res[i] = true;
    				break;
    			}
    		}
    	}
        
    	return res[s.length()];
    }
}

Search

    Table of Contents