单词拆分II

本文主要是介绍单词拆分II，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

 

 

变量简洁正确完整思路

一个问题所有具体解用dfs，dfs形参len对字符串进行如图dfs，len==0更新答案ans，dfs常用参数len，逆向枚举分割点i，如果后半段substr在dict中且前半段满足dpi，则加入答案ans1前端（ans1用deque）并dfs枚举前端，或者不要   精确定义 dpi 0到i字符串是否在dict中，dp0是空，dp1是第一个字符 len需要处理的字符串的长度 i 后半段第一个字符下标，也是dpi判断前半段，也是前半段的长度，这个定义非常重要   转移 - - a b c if dpj&&dict.count(substr(j ,i-j))dp i=1   初始化 dp0=1   画图

class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        int n=s.size();
        vector<int>dp(n+1,0);
        unordered_set<string>dict(wordDict.begin(),wordDict.end());
        dp[0]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<i;j++){
                if(dp[j]&&dict.count(s.substr(j,i-j))){
                    dp[i]=1;
                    break;
                }
            }
        }
        vector<string>ans;
        deque<string>ans1;
        dfs(n,ans,ans1,dp,s,dict);
        return ans;
    }
    void dfs(int len,vector<string>&ans,deque<string>&ans1,vector<int>&dp,string&s,unordered_set<string>&dict){
        if(len==0){
            string tmp;
            for(auto str:ans1){
                tmp+=str;
                tmp.push_back(' ');
            }
            tmp.pop_back();
            ans.push_back(tmp);
            return ;
        }
        for(int i=len-1;i>=0;i--){
            string tmp=s.substr(i,len-i);
            if(dp[i]&&dict.count(tmp)){
                ans1.push_front(tmp);
                dfs(i,ans,ans1,dp,s,dict);
                ans1.pop_front();
            }
        }
    }
};

 

踩过的坑 dfs回溯离不开画递归树，树的节点正是枚举什么的重要内容，这道题枚举ii 后半段第一个字符下标，也是dpi判断前半段，也是前半段的长度，这个定义非常重要 dfs中，常常用len作为第一个参数，然后枚举起点，这道题枚举i作为后半段的起点，如果 后半段在dict中且前半段满足dp就可以继续找，否则i--，反过来i++不行，因为排除了前半段，后半段不能用dp继续判断

 

 

这篇关于单词拆分II的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！