题目描述

给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。

算法1

我在这里写这个题解的原因呢不是我的解法有多么好，而是我在解题的时候遇到了两个问题，这两个错误也是一般很难debug出来的，所以我记下来提醒大家也防止自己忘记。

C++ 代码

//判断看两个string是否是其子串
bool check(string s,string s2){
       int  j=0;
        for(int i=0;i<s.size()&&j<s2.size();i++){
            if(s[i]==s2[j]) j++;
        }
        if(j==s2.size())return true ;
        return false;

    }
//这里是主函数
    string findLongestWord(string s, vector<string>& dictionary) {
//定义找到的最长字符串的长度max——num *****
         int max_num=0;
//把找到的结果都放进resall中去
         vector<string> resall;
         string res;
        for(int i=0;i<dictionary.size();i++){
            if(check(s,dictionary[i])&&dictionary[i].size()>=max_num)
            {
            resall.push_back(dictionary[i]);
            max_num =dictionary[i].size();
            }
        }
//这一步把长度不是最长的结果都去掉，我之后想到了用排序也可以，但是那是后话了*****
        for(int i=0;i<resall.size();i++){
            if(resall[i].size()!=max_num) resall.erase(resall.begin()+i--);
        }
//然后把剩下的排个序，找到字典序最短的
        sort(resall.begin(),resall.end(),[](string a,string b){
            return a<b;
        });
//如果不空的话就输出第一个
        if(!resall.empty()) res=resall[0];
        if(max_num!=0) return res;
        return "";

问题

算法很直白,但是我打星号的地方出现了两个问题：
1.如果这里的max_num定义成-1而不是0，可不可以为什么
2.resall.erase(resall.begin()+i–)这里为什么要i–

回答

1.不可以因为string，vector的size都是无符号整数，-1的第一位是1，因此是永远小于-1的

2.原因是erase函数的删除会改变整体的size，因此一方面会i的取值不是下一个string会往后跳并且当超过当时是size就会出循环，说起来可能比较难理解，强烈建议各位调试一下