leetcode 524. Longest Word in Dictionary through Deleting 子序列的确定 + 暴力查找比较

不念不忘少年蓝@ 2022-06-03 03:19 120阅读 0赞

Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

Example 1:  
Input:  
s = “abpcplea”, d = \[“ale”,”apple”,”monkey”,”plea”\]  
Output:  
“apple”  
Example 2:  
Input:  
s = “abpcplea”, d = \[“a”,”b”,”c”\]

Output:  
“a”  
Note:  
All the strings in the input will only contain lower-case letters.  
The size of the dictionary won’t exceed 1,000.  
The length of all the strings in the input won’t exceed 1,000.

本题题意很简单，就是做一个遍历，关键是子序列的判定

建议和[leetcode 522. Longest Uncommon Subsequence II 最长非公共子序列][leetcode 522. Longest Uncommon Subsequence II] 一起学习

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    
    using namespace std;
    
    class Solution 
    {
    public:
        string findLongestWord(string s, vector<string>& d) 
        {
            string res="";
            for (string sub : d)
            {
        
                if (sub.length() <= s.length() && check(sub, s))
                {
        
                    if (sub.length() > res.length())
                        res = sub;
                    else if (sub.length() == res.length())
                        res = res <= sub ? res : sub;
                }
            }
            return res;
        }
    
        bool check(string sub, string tar)
        {
        
            int i = 0;
            for (char c : tar)
            {
                if (sub[i] == c)
                    i++;
                if (i == sub.length())
                    return true;
            }
            return false;
        }
    };

[leetcode 522. Longest Uncommon Subsequence II]: http://blog.csdn.net/jackzhang_123/article/details/78821010