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

一、題目

給你一個字元串 s 和一個字元串數組 dictionary ，找出并傳回 dictionary 中最長的字元串，該字元串可以通過删除 s 中


的某些字元得到。


如果答案不止一個，傳回長度最長且字典序最小的字元串。如果答案不存在，則傳回空字元串。

 




示例 1：


輸入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]


輸出："apple"



示例 2：


輸入：s = "abpcplea", dictionary = ["a","b","c"]


輸出："a"


 

提示：


    1 <= s.length <= 1000
    
    1 <= dictionary.length <= 1000
    
    1 <= dictionary[i].length <= 1000

    s 和 dictionary[i] 僅由小寫英文字母組成

           

二、思路

• 複雜度O(d(n + m)),d為dictionary長度，n為s長度,m為dictionary裡面字元串的長度
• 循環周遊dictionnary，利用雙指針進行足以判斷即可。

三、代碼

class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
        int n = s.length();
        string ans = "";
        for (int i = 0; i < dictionary.size(); i++) {
             int l = 0, r = 0, m = dictionary[i].length();
            if (n < m) continue;
            while (l < n && r < m) {
                if (s[l] == dictionary[i][r]) r++; 
                l++;
            }
            if (r == m) {
                if (m > ans.length() || (m == ans.length() && ans > dictionary[i])) ans = dictionary[i];
            }
        }
        return ans;
    }
};