WordBreak题目
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”.
思路
设置一个数组re[]，re[i]存放的是截止到第i位是否能够匹配的信息。以上面为例，re[0]为false，因为‘l’在字典中不存在；re[3]就是true，因为’leet‘在dict中可以匹配。于是，，第i为的值只与它之前的i-1位有关，我们可以自底向上推出最后一位的值，并返回即结果。
代码class Solution {public:void mark(string s,vector<bool> &re,int n,unordered_set<string> &dict){unordered_set<string>::iterator ite;ite=dict.find(s.substr(0,n+1));if (ite!=dict.end()) {re[n]=true;return;}else {for (int i=0;i<n;i++){if (re[i]){ite=dict.find(s.substr(i+1,n-i));if (ite!=dict.end()) {re[n]=true;return;}}}}}bool wordBreak(string s, unordered_set<string> &dict) {int len = s.length();vector<bool> re(len,false);for (int i=0;i<len;i++){mark(s,re,i,dict);}return re[len-1];}};运行结果
妩媚动人，让我感受到了大自然的神奇。
