题解 | #单词拆分(一)#

单词拆分(一)

http://www.nowcoder.com/practice/c0d32c1ce5744472a01b2351a2c2767f

题意

给定字符串能否由给定字典中的单词拼接而成.

限制:

字符串长度不大于500

字典单词数不大于1000,每个单词长度不大于20

方法

dfs

通过递归,每次匹配字典里所有单词,一旦匹配成功, 从匹配成功的下标递归搜索下一个位置,如果完全匹配了则返回匹配成功.

代码

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);
    }
};

复杂度分析

设字符串长度为m

时间复杂度: 最坏情况下,只有递归的最后一层才不匹配,所有为 $O (n^{m})$

空间复杂度: 主要消耗在递归深度上,所以空间复杂度为 $O (m)$

枚举搜索字符串

如果字符串是由字典中的构成,那么每次匹配掉一部分,如果能完全匹配掉,则表明字符串是能够由字典中的单词构成.

以样例数据 "nowcoder"为例

初始化时, 空字符串为匹配完成

于是对这个位置尝试匹配"now"和"coder"匹配,匹配成功,标记长度为3的字符串匹配成功

当遍历到字符串的长度为三时,再次尝试匹配"now"和"coder",匹配成功,标记长度为8的字符串匹配成功

alt

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param dic string字符串vector 
     * @return bool布尔型
     */
    bool wordDiv(string s, vector<string>& dic) {
        vector<int> ok(s.length()+1,0);
        ok[0] = 1; // 空字符串匹配成功
        for(int i = 0;i < s.length();i++){
            if(!ok[i])continue; // 能匹配到这个位置
            for(int j = 0;j < dic.size();j++){ // 尝试每个字典
                if(dic[j].length()+i > s.length())continue; // 忽略超长的字符串
                bool match = true; // 匹配
                for(int k = 0 ;k<dic[j].length();k++){
                    if(dic[j][k] != s[i+k]) { // 有字符不同
                        match = false;
                        break;
                    }
                }
                if(match) { // 所有字符相同
                    ok[i+dic[j].length()] = true;
                }
            }
        }
        return ok[s.length()];
    }
};