算法学习过程心得体会

//这个 KMP 函数的返回值是模式串 t 在主串 s 中第一次出现的起始位置（从 0 开始计数）
int kmp(const string& s, const string& t){
        int s_length = s.size(), t_length = t.size();
        if (t_length == 0) return 0;
        if (s_length < t_length) return -1;

        //求next数组(从下标0开始)
        vector<int> next(t_length + 1);//大小 + 1防止堆和缓冲区溢出
        //next[t_length]的值是t字符串的最大前后缀公共长度
        next[0] = -1;
        int i = 0, j = -1;//i是当前正在计算next值的位置；j是前缀指针，当前已经匹配的长度
        while(i < t_length){
            if(j == -1 || t[i] == t[j]){//j = -1表示没有匹配的前缀
                next[++i] = ++j;
            }else{
                j = next[j];
            }
        }

        //KMP匹配，求t字符串在s字符串中出现的第一次位置
        i = 0, j = 0;//i是主串指针，j是匹配串指针
        while(i < s_length && j < t_length){
            if(j == -1 || s[i] == t[j]){
                ++i, ++j;
            }else{
                j = next[j];
            }
        }
        
        return j == t_length ? i - j : -1;
    }
};

int GetNext(char ch[], int length, int next[]){
    next[1] = 0;
    int i = 1, j = 0;
    while(i <= length){
        if(j==0 || ch[i] == ch[j]){
            next[++i] = ++j;
        }else{
            j = next[j];
        }
    }
}

代码如下：

class Solution {
private:
    vector<string> dic = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public:
    vector<string> letterCombinations(string digits) {
        int n = digits.size();
        if(n == 0)  return {};

        vector<string> ans;
        string path;
        auto dfs = [&](this auto&& dfs, int i)->void{
            if(i == n){
                ans.emplace_back(path);
                return;
            }
            int idx = digits[i] - '0';
			for(int j = 0; j < dic[idx].size(); ++j){
				path += dic[idx][j];
				dfs(i + 1);
                path.pop_back();// 回溯，移除最后一个字母！ 必须要回溯！
			}
        };

        dfs(0);//回溯的入口！
        return ans;
    }
};