Leetcode 139. WordBreak 解法和思路

原文的题干如下：

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

大致意思是给定一个非空字符串 s ，和一个词典 wordDict ，词典包含一系列的词。需要找出的是这个字符串s可否完全用词典中的词分隔成单个单词。

例子

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
说明：leetcode -> leet code
复制代码

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
说明：applepenapple -> apple pen apple
复制代码

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
说明: catsandog中的cat sand和dog互相有重叠，无法区隔
复制代码

2 错误的解法

最开始没有细想，用了比较暴力的解法，

class Solution {
public:
	string reduce(string s, vector<string>& wordDict) {
		for (vector<string>::iterator iter = wordDict.begin(); iter != wordDict.end(); ++iter) {
			size_t pos = s.find(*iter);
			if (pos != string::npos) {
				string left = s.substr(0, pos);
				string right = s.substr(pos + (*iter).size());
				if (evaluate(left, right, wordDict) == "OK") {
					return "";
				}
			}
		}
		return s;
	}

	string evaluate(string left, string right, vector<string>& wordDict) {
		if (reduce(left, wordDict).size() == 0 && reduce(right, wordDict).size() == 0) {
			return "OK";
		}
		return "BAD";
	}
	
	bool wordBreak(string s, vector<string>& wordDict) {
		string result = reduce(s, wordDict);
		if (result == "") {
			return true;
		}
		return false;
	}
};
复制代码

之所以想到这个解法，主要是因为第一联想到的是编译原理中的语法分析。有一些文法使用一种称为 递归下降 (recursive descent)的简单算法就很容易进行分析。这种算法的实质是将每一个文法产生式转变成递归函数的一个子句 [1] 。简单来说就是把所有可能性表示成一棵树，在单词不能再分割的时候，使之成为叶子节点，然后依次回溯求值，最终得到最开始的字符串是否是可分割的。

这道题一共有36个Test Case，我的代码执行到第30个用例的时候就会开始Time Exceeded了，原因很明显：在极端的用例情况，树的分支太多太深，遍历全部路径会花费很长时间。

3 动态规划解法

因此回到最开始，这道题的良解之一是 动态规划 (DP，Dynamic Programming)。

动态规划是一种算法设计技术，该技术认为最优化问题的任一实例的最优解，都是由其子实例的最优解构成的 [2] 。文字描述起来比较难懂，下面就这个问题举例说明：

输入: s = "ccaccc", wordDict = ["cc", "ac"]
输出: true
说明：ccaccc -> cc ac cc
复制代码

按照动态规划的常见思路，我们一般会把目标集合划分为下标从0到最大值不断迭代的对象。通常我们需要一个初始值F(0)，这里虽然题干规定s一定不为空，但这里我们可以令F(0)=True，也就是没有任何字符串的时候，输出可以为True。然后依次递增下标，每次递增都从当前下标遍历词典中的词，只要当前下标的位置可以找到词典中的词，并且当前下标之前也是一个可分对象，就可以认为找到的这个词典的词，以及下标之前的部分，是本题的解之一。

下面用代码表述一下这个解法：

class Solution {
public:	
	bool wordBreak(string s, vector<string>& wordDict) {
		size_t n = s.size();
		vector<int> dp(n+1, 0);
		dp[0] = 1;
		for (size_t i = 0; i < n; ++i) {
			for (vector<string>::iterator iter = wordDict.begin(); iter != wordDict.end(); ++iter) {
				if(s.substr(i).find(*iter)==0 && dp[i]) {
					dp[i + (*iter).size()] = 1;
				}
			}
		}
		return bool(dp[n]);
	}
};
复制代码

可以发现该解法已经属于较良好解法。

当然，可以看到前方仍然有12%的Runtime，因此应该还存在改进空间，大家刷到这题的时候也可以自己再多方面尝试一下。