C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2022-04-10

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param dic string字符串vector 
     * @return bool布尔型
     */
    bool wordDiv(string s, vector<string>& dic) {
        // write code here
        int n = s.length();
        vector<bool> dp(n + 1, false);
        dp[0] = true;
        for (int i=0; i<n; ++i) {
            if (!dp[i]) {
                continue;
            }
            
            for (auto& word : dic) {
                if (s.substr(i, word.length()) == word) {
                    dp[i + word.length()] = true;
                }
            }
        }
        
        return dp[n];
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 400KB, 提交时间: 2022-01-16

class Solution {
public:

    bool dfs(const string & s,int idx,vector<string> & dic){ // 递归 字符串 下标 字典
      if(idx == s.length())return true; // 完成匹配
      for(int i = 0;i<dic.size();i++){ // 遍历字典
        if(idx+dic[i].length() > s.length())continue;
        bool match = true;
        for(int j = 0 ; j<dic[i].length();j++){
          if(s[idx+j] != dic[i][j]){ // 字符匹配失败
            match = false;
            break;
          }
        }
        if(match){
          bool r = dfs(s,idx+dic[i].length(),dic); // 递归匹配
          if(r)return r;
        }
      }
      return false;
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @param dic string字符串vector
     * @return bool布尔型
     */
    bool wordDiv(string s, vector<string>& dic) {
      return dfs(s,0,dic);
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 412KB, 提交时间: 2022-06-10

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param dic string字符串vector 
     * @return bool布尔型
     */
    bool wordDiv(string s, vector<string>& dic) {
        // write code here
        int n=s.size();
        vector<bool> dp(n+1,false);
        dp[0]=true;
        for(int i=0;i<n;i++){
            if(!dp[i]) continue;
            for(auto& w :dic){
                if(s.substr(i,w.size())==w){
                    dp[i+w.size()]=true;
                }
       }
        }
            return dp[n];
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 412KB, 提交时间: 2021-12-22

#include <algorithm>

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param dic string字符串vector 
     * @return bool布尔型
     */
    bool wordDiv(string s, vector<string>& dic) {
        int i,j,len=s.length();
        bool res=false;
        if(len)
        {
            vector<bool> dp(len+1,false);
            dp[0]=true;
            for(i=1;i<=len;i++)
                for(j=i-1;j>=0&&(!dp[i]);j--)
                    dp[i]=dp[j]&&(find(dic.begin(),dic.end(),s.substr(j,i-j))!=
                                       dic.end());
            res=dp[len];
        }
        return res;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 416KB, 提交时间: 2022-05-29

class Solution {
public:
    bool dfs(const string & s,int idx,vector<string> & dic){ // 递归 字符串 下标 字典
      if(idx == s.length())return true; // 完成匹配
      for(int i = 0;i<dic.size();i++){ // 遍历字典
        if(idx+dic[i].length() > s.length())continue;
        bool match = true;
        for(int j = 0 ; j<dic[i].length();j++){
          if(s[idx+j] != dic[i][j]){ // 字符匹配失败
            match = false;
            break;
          }
        }
        if(match){
          bool r = dfs(s,idx+dic[i].length(),dic); // 递归匹配
          if(r)return r;
        }
      }
      return false;
    }
    bool wordDiv(string s, vector<string>& dic) {
      return dfs(s,0,dic);
    }
};