Word Break （重重重）-白红宇

Word Break （重重重）

阅读量：4107 次

发布时间：2019-05-25

本文共 1643 字，大约阅读时间需要 5 分钟。

题目：

解法一：

深搜

剪枝：如果s中含有dict中不包含的字符直接输出false.

class Solution { public:	 int flag = 0;	 bool wordBreak(string s, unordered_set
   
     &dict) {		 int a[26];		 for (int i = 0; i < 26; i++)			 a[i] = 0;		 for (int i = 0; i < s.length(); i++)			 a[s[i]-'a'] = 1;		 for (unordered_set
    
     ::iterator it = dict.begin(); it != dict.end(); it++)		 {			 for (int j = 0; j < it->length(); j++)			 {				 string temp = *it;				 a[temp[j]-'a'] = 0;			 }		 }		 int temp = 0;		 for (int i = 0; i < 26; i++)		 {			 temp += a[i];		 }		 if (temp > 0)			 return false;		 search(s, dict);		 if (flag == 1)			 return true;		 return false;		 	 }	 void search(string s, unordered_set
     
       &dict)	 {		 if (flag == 1)			 return;		 if (s == "")		 {			 flag = 1;		 }		 else		 {			 for (unordered_set
      
       ::iterator it = dict.begin(); it != dict.end(); it++)			 {				 string tempstr = s.substr(0, it->length());				 if (tempstr == *it)				 {					 tempstr = s.substr(it->length(), s.length() - it->length());					 search(tempstr, dict);				 }			 }		 }	 } };

解法二：

DP：

dp[i] 表示源串的前i个字符可以满足分割，那么 dp[ j ] 满足分割的条件是存在k 使得 dp [k] && substr[k,j]在字典里。

// 第二版 参考leetcode官网上的答案class Solution { public:bool wordBreak(string s, unordered_set
   
     &dict) {    vector
    
      wordB(s.length() + 1, false);    wordB[0] = true;    for (int i = 1; i < s.length() + 1; i++) {        for (int j = i - 1; j >= 0; j--) {            if (wordB[j] && dict.find(s.substr(j, i - j)) != dict.end()) {                wordB[i] = true;                break; //只要找到一种切分方式就说明长度为i的单词可以成功切分，因此可以跳出内层循环。            }        }    }    return wordB[s.length()];    }};