Leetcode (524) -- match the longest word in the dictionary by deleting letters

Leetcode（524）—— Delete the longest letters from the dictionary

subject

Give you a string s And an array of strings dictionary , Find out and return to dictionary The longest string in , The string can be deleted s Some characters in get .

If there is more than one answer , Returns the string with the longest length and the smallest alphabetical order . If the answer doesn't exist , Returns an empty string .

Example 1：

Input ：s = “abpcplea”, dictionary = [“ale”,“apple”,“monkey”,“plea”]
Output ：“apple”

Example 2：

Input ：s = “abpcplea”, dictionary = [“a”,“b”,“c”]
Output ：“a”

Tips ：

• $1$ <= s.length <= $1000$
• $1$ <= dictionary.length <= $1000$
• $1$ <= dictionary[i].length <= $1000$
• s and dictionary[i] It's only made up of lowercase letters

Answer key

Method 1 ： greedy + Double pointer

Ideas

​​   According to the meaning , We need to solve two problems ：

• How to determine $\text{dictionary}$ String in $t$ Can I delete $s$ Some characters in get ;
• How to find the string with the longest length and the smallest dictionary order .

​​   The first $1$ The first problem is actually judgment $t$ Whether it is $s$ The subsequence . So as long as you can find any one $t$ stay $s$ The way they appear in , It can be considered that $t$ yes $s$ The subsequence . And when we match from front to back , You can find that every time Greedily match the top character （ Until I find $s$ The first place in $dictionary[x][j]$ The right position ） Is the optimal decision .

Assume that you currently need to match characters $c$, And characters $c$ stay $s$ Position in $x_1$ and $x_2$ appear （$x_1<x_2$）, So greedy $x_1$ It is the optimal solution. , because $x_2$ Characters that can be accessed later ,$x_1$ Can also get , And through $x_1$ And $x_2$ Optional characters between , There is more hope that the match will succeed .

​​   such , We initialize two pointers $i$ and $j$, Point to respectively $t$ and $s$ Initial position . Match greedily every time , If the match is successful $i$ and $j$ Move right at the same time , matching $t$ Next position of , If the match fails, then $j$ Move right ,$i$ unchanged , Try to use $s$ Match the next character of $t$ .

​​   In the end, if $i$ Move to $t$ At the end of , shows $t$ yes $s$ The subsequence .

​​   The first $2$ Questions can be traversed $\text{dictionary}$ String in , And maintain the string with the longest current length and the smallest dictionary order to find .

Code implementation

My own ：

class Solution {
    
public:
    string findLongestWord(string s, vector<string>& dictionary) {
    
        //  Traverse  dictionary  String in , Then compare them one by one  s , And judge whether it can be deleted  s  Some characters in get 
        // maxL  The string with the longest length and the smallest alphabetical order is in  dictionary  Subscript in  
        int maxL = -1, ptr, size_d = dictionary.size(), size_s = s.size();
        for(int n = 0; n < size_d; n++){
    
            //  First compare the current string with  maxL  Represents the length of the string 
            //  If the current string length is shorter than  maxL  Or both are equal in length but the alphabetic order is greater than or equal to  maxL  Then find the next string 
            if(maxL != -1 && (dictionary[n].size() < dictionary[maxL].size() || 
            (dictionary[n].size() == dictionary[maxL].size() && dictionary[n] >= dictionary[maxL]))) continue;
            ptr = 0;    //  Point to the current string 
            for(int i = 0; i < size_s && ptr < dictionary[n].size(); i++)
                if(s[i] == dictionary[n][ptr]) ptr++;
            if(ptr == dictionary[n].size()) maxL = n;
        }
        return maxL == -1? "": dictionary[maxL];
    }
};

Complexity analysis

Time complexity ：$O(d\times (m+n))$, among $d$ Express $\text{dictionary}$ The length of ,$m$ Representation string $s$ The length of ,$n$ Express $\text{dictionary}$ Average length of string in . We need to traverse $\text{dictionary}$ Medium $d$ A string , Each string requires $O(n+m)$ To determine whether the string is $s$ The subsequence .
Spatial complexity ：$O(1)$

Method 2 ： Double pointer + Sort preprocessing

Ideas

​​   On the basis of method one , We try to pass on $\text{dictionary}$ Preprocessing , To optimize the $2$ How to deal with these problems .
   We can first $\text{dictionary}$ Sort according to the descending order of string length and the ascending order of dictionary order , Then find the first qualified string from the front to the back and return it directly .

Code implementation

My own ：

class Solution {
    
public:
    string findLongestWord(string s, vector<string>& dictionary) {
    
        //  Sort 
        sort(dictionary.begin(), dictionary.end(), 
        [](string& A, string& B){
    return A.size() > B.size() || (A.size() == B.size() && A < B);});
        int ptr, size_d = dictionary.size(), size_s = s.size();
        for(int n = 0; n < size_d; n++){
    
            ptr = 0;    //  Point to the current string 
            for(int i = 0; i < size_s && ptr < dictionary[n].size(); i++)
                if(s[i] == dictionary[n][ptr]) ptr++;
            if(ptr == dictionary[n].size()) return dictionary[n];
        }
        return "";
    }
};

Complexity analysis

Time complexity ：$O(d\times m\times logd+d\times (m+n))$, among $d$ Express $\text{dictionary}$ The length of ,$m$ Express $s$ The length of ,$n$ Express $\text{dictionary}$ Average length of string in . We need to $O(d\times m\times \log d)$ Time to sort $\text{dictionary}$; In the worst case , We need to $O(d\times (m+n))$ To find the first qualified string .
Spatial complexity ：$O(d\times m)$, The cost of sorting .

Method 3 ： Double pointer +DP Preprocessing

Ideas

​​   On the basis of method one , We consider by pairing strings $s$ Preprocessing , To optimize the $1$ How to deal with these problems .

​​   Consider the previous double pointer approach , We notice that we have a lot of time for $s$ Next matching character found in .

​​   In this way, we can preprocess , obtain ： For strings $s$ Every position of , Start at the first position of the character （ Including the location ）.

​​   We can use the method of dynamic programming to realize preprocessing , Make $f[i][j]$ Representation string $s$ From the middle $i$ Start with the following characters $j$ First occurrence . During state transition , If $s$ Middle position $i$ The character is $j$, that $f[i][j]=i$, otherwise $j$ Appear in position $i+1$ Start back , namely $f[i][j]=f[i+1][j]$; So we have to reverse the dynamic planning , Enumerate from back to front $i$.

So we can write State transition equation ：
$$f[i][j]=\{\begin{array}{ll}i,& s[i]=j\\ f[i+1][j],& s[i]\ne j\end{array}$$

​​   Assume that the subscript is from $0$ Start , that $f[i][j]$ There is $0\le i\le m-1$, For boundary States $f[m-1][..]$, We make $f[m][..]$ The value of is $m$, Give Way $f[m-1][..]$ Transfer normally . So if $f[i][j]=m$, From position $i$ No characters after start $j$.

​​   such , We can use $f$ Array , Every time $O(1)$ Jump to the next position , Until the position changes to $m$ or $t$ Every character in is matched successfully .

Code implementation

Leetcode Official explanation ：

class Solution {
    
public:
    string findLongestWord(string s, vector<string>& dictionary) {
    
        const int n = s.size();
        int next[26];
        fill_n(next, 26, -1);
        int trans[n + 1][26];
        fill_n(trans[n], 26, -1);
        for (int i = n - 1;0 <= i;--i) {
    
            next[s[i] - 'a'] = i + 1;
            copy_n(next, 26, trans[i]);
        }
        string_view ans = "";
        for (const auto& e : dictionary) {
    
            int state = 0;
            for (char c : e) {
    
                state = trans[state][c - 'a'];
                if (state == -1) break;
            }
            if (state == -1) continue;
            if (e.size() > ans.size() || e.size() == ans.size() && e < ans)
                ans = e;
        }
        return string(ans);
    }
};

My own （STL edition ）：

class Solution {
    
public:
    string findLongestWord(string s, vector<string>& dictionary) {
    
        int maxL = -1, ptr, s_size = s.size(), d_size = dictionary.size();
        vector<vector<int>> s_letter(s_size, vector<int>(26, -1));
        for(int n = s_size-1; n >= 0; n--){
    
            if(n != s_size-1) s_letter[n] = s_letter[n+1];
            s_letter[n][s[n]-'a'] = n;
        }
        for(int n = 0; n < d_size; n++){
    
            if(maxL != -1 && (dictionary[n].size() < dictionary[maxL].size() || 
            (dictionary[n].size() == dictionary[maxL].size() && dictionary[n] >= dictionary[maxL]))) continue;
            ptr = 0;
            for(int i = 0; i < s_size && ptr < dictionary[n].size(); i++){
    
                i = s_letter[i][dictionary[n][ptr]-'a'];
                if(i == -1) break;
                ptr++;
            }
            if(ptr == dictionary[n].size()) maxL = n;
        }
        return maxL == -1? "": dictionary[maxL];
    }
};

My own （ Basic array type ）：

class Solution {
    
public:
    string findLongestWord(string s, vector<string>& dictionary) {
    
        int maxL = -1, ptr, s_size = s.size(), d_size = dictionary.size();
        int s_letter[s_size][26];
        fill_n(s_letter[s_size-1], 26, -1);    // Just assign values to the last array , There is DP It will be assigned to other arrays during processing 
        for(int n = s_size-1; n >= 0; n--){
    
            if(n != s_size-1) copy_n(s_letter[n+1], 26, s_letter[n]);
            s_letter[n][s[n]-'a'] = n;
        }
        for(int n = 0; n < d_size; n++){
    
            if(maxL != -1 && (dictionary[n].size() < dictionary[maxL].size() || 
            (dictionary[n].size() == dictionary[maxL].size() && dictionary[n] >= dictionary[maxL]))) continue;
            ptr = 0;
            for(int i = 0; i < s_size && ptr < dictionary[n].size(); i++){
    
                i = s_letter[i][dictionary[n][ptr]-'a'];
                if(i == -1) break;
                ptr++;
            }
            if(ptr == dictionary[n].size()) maxL = n;
        }
        return maxL == -1? "": dictionary[maxL];
    }
};

Complexity analysis

Time complexity ：$O(m\times |\Sigma |+d\times n)$, among $d$ Express $\text{dictionary}$ The length of ,$\Sigma$ Is a character set , In this question, the string only contains English lowercase letters , so $|\Sigma |=26$;$m$ Representation string $s$ The length of ,$n$ Express $\text{dictionary}$ Average length of string in . The time complexity of preprocessing is $O(m\times |\Sigma |)$; Judge $d$ Whether the string is $s$ The event complexity of the subsequence of is $O(d\times n)$.
Spatial complexity ：$O(m\times \mid \Sigma \mid )$, To dynamically plan the cost of arrays .