题目描述

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

样例

示例 1:

输入:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

输出: 
"apple"
示例 2:

输入:
s = "abpcplea", d = ["a","b","c"]

输出: 
"a"

算法1

(双指针) $O(n)$

C++ 代码

class Solution {
public:
    string findLongestWord(string s, vector<string>& d) {
        if(d.size()==0) return "";
        string res="";
        for(auto sub:d){
            if(issubstr(s,sub)==true)
                if(sub.size()>res.size()||sub.size()==res.size()&&sub<res)
                    res = sub;
                   }
        return res;
    }
    bool issubstr(string s,string d){
        int i,j;
         for( i=0,j=0;i<s.size();i++){
             if(s[i]==d[j]) j++;
             if(j==d.size()) break; 
         }
        //cout<<j<<' '<<d.size()<<endl;
        if(j>=d.size())
            return true;
        return false;
    }
};

改进

class Solution {
public:
    string findLongestWord(string s, vector<string>& d) {
        //if(d.size()==0) return "";
        string res="";
        for(auto sub:d)
            if(issubstr(s,sub)==true)
                if(sub.size()>res.size()||sub.size()==res.size()&&sub<res)
                    res = sub;
        return res;
    }
    bool issubstr(string s,string d){
        int i,j;
         for( i=0,j=0;i<s.size();i++)
             if(s[i]==d[j]) j++;
        return j==d.size();
    }
};