力扣 524. 通過删除字母比對到字典裡最長單詞 dp

https://leetcode-cn.com/problems/longest-word-in-dictionary-through-deleting/

思路：經典題目了，其實就是求滿足題意的子序列嘛。直接預處理出 d p i , j dp_{i,j} dpi,j​數組， d p i , j dp_{i,j} dpi,j​表示從第 i i i個位置開始第一個字元 j j j所對應的位置，顯然有：

d p i , j = { d p i , j = d p i + 1 , j ,      i f   s i ≠   j d p i , j = i ,      i f   s i   =   j dp_{i,j}=\left\{ \begin{aligned} & dp_{i,j}=dp_{i+1,j}, \ \ \ \ if\ s_i \neq\ j \\ & dp_{i,j}=i, \ \ \ \ if\ s_i\ =\ j \\ \end{aligned} \right. dpi,j​={​dpi,j​=dpi+1,j​,    if si​​= jdpi,j​=i,    if si​ = j​

那麼在判斷子序列的時候就可以通過位置和字元 O ( 1 ) O(1) O(1)轉移了。

class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
        int n=s.size();
        vector<array<int,26>> idx(n);
        for(int i=0;i<26;i++)
            idx[n-1][i]=n;
        idx[n-1][s[n-1]-'a']=n-1;
        for(int i=n-2;i>=0;i--)
        {
            copy(idx[i+1].begin(),idx[i+1].end(),idx[i].begin());
            idx[i][s[i]-'a']=i;
        }
        string ans;
        for(const string& str:dictionary)
        {
            int pos=0,m=str.size(),i=0;
            for(i=0;i<m;i++)
            {
                pos=idx[pos][str[i]-'a']+1;
                if(pos>=n)
                    break;
            }
            if((pos<n||(pos==n&&i==m-1))&&(str.size()>ans.size()||(str.size()==ans.size()&&str<ans)))
                ans=str;
        }
        return ans;
    }
};