Li Kou 139: word splitting

Power button 139 topic ： Word splitting

Title Description

Give you a string s And a list of strings wordDict As a dictionary . Please judge whether you can use the words in the dictionary to splice s .

Be careful ： It is not required to use all the words in the dictionary , And the words in the dictionary can be reused .

I/o sample

 Input : s = "leetcode", wordDict = ["leet", "code"]
 Output : true
 explain :  return  true  because  "leetcode"  Can be  "leet"  and  "code"  Stitching into .

 Input : s = "applepenapple", wordDict = ["apple", "pen"]
 Output : true
 explain :  return  true  because  "applepenapple"  Can be  "apple" "pen" "apple"  Stitching into .
      Be careful , You can reuse the words in the dictionary .

 Input : s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
 Output : false

Solution 1 , Use hash+ iteration , May succeed but OJ will not pass

 // Use hash Table for processing , The local delivery is OK, but the delivery force deduction will make an error 
    bool wordBreak(string s, vector<string>& wordDict) 
    {
    
        unordered_set<string>sets;

        // Save the data in the dictionary to hash In the table 
        for(auto i:wordDict)
        {
    
            sets.insert(i);
        }

        string tempStr=s;
        string resStr=s;


        auto index=sets.begin();

        while(index!=sets.end())
        {
    
            string strs=*index;
            
            // Take a part of 
            int length=strs.size();
            int resLength=resStr.size();

            string saveStr=resStr;
            //substr If no character is specified, it is truncated to the end 
            tempStr=resStr.substr(0,length);

            if(length>resLength)
            {
    
                index++;
                continue;
            }
            resStr=resStr.substr(length);


            if(tempStr==strs)
            {
    
                resStr=resStr;
                index=sets.begin();
                if(resStr.empty())
                {
    
                    return true;
                }
            }
            else{
    
                resStr=saveStr;
                ++index;
            }
        }
        return false;

    }

solution 2： Dynamic programming

    bool wordBreak2(string s, vector<string>& wordDict) 
    {
    
        // First set up hash Save array 
        unordered_set<string>sets;
        for(auto word:wordDict)
        {
    
            sets.insert(word);
        }

        // Create dynamic programming array , The length is size+1
        // The conversion condition is set to  dp[i]=dp[j]&&checks(s[j..i-1])
        // The length of the string is used as the transition condition 
        // Initial conditions  dp[0]=true
        vector<bool>dp(s.size(),false);
        dp[0]=true;

        for(int i=1;i<=s.size();i++)
        {
    
            for(int j=0;j<i;j++)
            {
    
                // utilize find Function to find whether the subset exists 
                if(dp[j]&&sets.find(s.substr(j,i-j))!=sets.end())
                {
    
                    dp[i]=true;
                    break;
                }
            }
        }

        // The last one indicates whether to judge success 
        return dp[s.size()];
    }

Solution 3 , Dynamic programming + Mnemonic backtracking

    // Memory based backtracking dynamic programming implementation 
    bool wordBreak3(string s, vector<string>& wordDict) 
    {
    
        // Create dynamic programming array , The length is size+1
        // The conversion condition is set to  dp[i]=dp[j]&&checks(s[j..i-1])
        // The length of the string is used as the transition condition 
        // Initial conditions  dp[0]=true
        vector<bool>dp(s.size(),false);
        dp[0]=true;

        for(int i=0;i<s.size();i++)
        {
    
            // Skip directly the unset value , Shorten the operation time 
            if(!dp[i])
            {
    
                continue;
            }

            // It is mainly from this step to directly find out whether the cut string matches. If so, the current length is set to 1
            for(auto &word:wordDict)
            {
    
                if(word.size()+i<=s.size()&&s.substr(i,word.size())==word)
                {
    
                    dp[i+word.size()]=true;
                }
            }
        }
        return dp[s.size()];
    }
};