通过删除字母匹配到字典里最长单词 图解题解

这道题到底在问什么

输入

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

输出

"apple"

最优解：一步一步想明白

1. 3记住口诀:内层双指针判子序列,外层比长度、平局比字典序。下面每帧都在套它。
2. 4上面这排是源串 s 的每个字母。我们要逐个拿字典里的候选词,放进来用双指针扫 s,看它能不能整词对上。绿色代表对上的字母,蓝色代表扫过但没用上的。
3. 5轮到字典第 1 个候选 ale（长度 3）。两个指针都从头开始:i 指它的第一个字母 a,j 从 s 的第 0 位往右扫,去把这些字母依次找出来。
4. 6s 第 0 位是 a,正好等于 ale 当前要找的 a,命中!这一格变绿,i 前进到 1。下一个要找 l。
5. 7s 第 1 位是 b,不等于现在要找的 l,这一格用不上,标蓝跳过,j 继续右移。i 仍然停在 1。
6. 8s 第 2 位是 p,不等于现在要找的 l,这一格用不上,标蓝跳过,j 继续右移。i 仍然停在 1。
7. 9s 第 3 位是 c,不等于现在要找的 l,这一格用不上,标蓝跳过,j 继续右移。i 仍然停在 1。
8. 10s 第 4 位是 p,不等于现在要找的 l,这一格用不上,标蓝跳过,j 继续右移。i 仍然停在 1。
9. 11s 第 5 位是 l,正好等于 ale 当前要找的 l,命中!这一格变绿,i 前进到 2。下一个要找 e。
10. 12s 第 6 位是 e,正好等于 ale 当前要找的 e,命中!这一格变绿,i 前进到 3。ale 的字母全部对上了。
11. 13ale 是子序列,而且比之前的最优更长（或同长更靠前）,刷新最优 = ale。
12. 14轮到字典第 2 个候选 apple（长度 5）。两个指针都从头开始:i 指它的第一个字母 a,j 从 s 的第 0 位往右扫,去把这些字母依次找出来。
13. 15s 第 0 位是 a,正好等于 apple 当前要找的 a,命中!这一格变绿,i 前进到 1。下一个要找 p。
14. 16s 第 1 位是 b,不等于现在要找的 p,这一格用不上,标蓝跳过,j 继续右移。i 仍然停在 1。
15. 17s 第 2 位是 p,正好等于 apple 当前要找的 p,命中!这一格变绿,i 前进到 2。下一个要找 p。
16. 18s 第 3 位是 c,不等于现在要找的 p,这一格用不上,标蓝跳过,j 继续右移。i 仍然停在 2。
17. 19s 第 4 位是 p,正好等于 apple 当前要找的 p,命中!这一格变绿,i 前进到 3。下一个要找 l。
18. 20s 第 5 位是 l,正好等于 apple 当前要找的 l,命中!这一格变绿,i 前进到 4。下一个要找 e。
19. 21s 第 6 位是 e,正好等于 apple 当前要找的 e,命中!这一格变绿,i 前进到 5。apple 的字母全部对上了。
20. 22apple 是子序列,而且比之前的最优更长（或同长更靠前）,刷新最优 = apple。
21. 23轮到候选 monkey,它要找的第一个字母是 m。可整条 s 从头扫到尾,a、b、p、c、p、l、e、a 里没有一个 m,i 一直卡在 0。
22. 24monkey 的第一个字母都凑不齐,自然不是子序列,淘汰。最优依旧是 apple。
23. 25轮到字典第 4 个候选 plea（长度 4）。两个指针都从头开始:i 指它的第一个字母 p,j 从 s 的第 0 位往右扫,去把这些字母依次找出来。
24. 26s 第 0 位是 a,不等于现在要找的 p,这一格用不上,标蓝跳过,j 继续右移。i 仍然停在 0。
25. 27s 第 1 位是 b,不等于现在要找的 p,这一格用不上,标蓝跳过,j 继续右移。i 仍然停在 0。
26. 28s 第 2 位是 p,正好等于 plea 当前要找的 p,命中!这一格变绿,i 前进到 1。下一个要找 l。
27. 29s 第 3 位是 c,不等于现在要找的 l,这一格用不上,标蓝跳过,j 继续右移。i 仍然停在 1。
28. 30s 第 4 位是 p,不等于现在要找的 l,这一格用不上,标蓝跳过,j 继续右移。i 仍然停在 1。
29. 31s 第 5 位是 l,正好等于 plea 当前要找的 l,命中!这一格变绿,i 前进到 2。下一个要找 e。
30. 32s 第 6 位是 e,正好等于 plea 当前要找的 e,命中!这一格变绿,i 前进到 3。下一个要找 a。
31. 33s 第 7 位是 a,正好等于 plea 当前要找的 a,命中!这一格变绿,i 前进到 4。plea 的字母全部对上了。
32. 34plea 是子序列,但它没有比当前最优 apple 更长、平局也没更靠前,最优不变。
33. 35四个候选都试完。ale 是子序列但只有 3 个字母,apple 是子序列有 5 个,monkey 淘汰,plea 是子序列但只有 4 个。最长的就是 apple,绿色高亮的就是它在 s 里对上的那 5 个字母。答案 apple。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def findLongestWord(self, s: str, dictionary: List[str]) -> str:
        def check(s: str, t: str) -> bool:
            m, n = len(s), len(t)
            i = j = 0
            while i < m and j < n:
                if s[i] == t[j]:
                    i += 1
                j += 1
            return i == m

        ans = ""
        for t in dictionary:
            if check(t, s) and (len(ans) < len(t) or (len(ans) == len(t) and ans > t)):
                ans = t
        return ans

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
        string ans = "";
        auto check = [&](const string& s, const string& t) {
            int m = s.size(), n = t.size();
            int i = 0;
            for (int j = 0; i < m && j < n; ++j) {
                if (s[i] == t[j]) {
                    ++i;
                }
            }
            return i == m;
        };
        for (auto& t : dictionary) {
            int a = ans.size(), b = t.size();
            if (check(t, s) && (a < b || (a == b && ans > t))) {
                ans = t;
            }
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        String ans = "";
        for (String t : dictionary) {
            int a = ans.length(), b = t.length();
            if (check(t, s) && (a < b || (a == b && t.compareTo(ans) < 0))) {
                ans = t;
            }
        }
        return ans;
    }

    private boolean check(String s, String t) {
        int m = s.length(), n = t.length();
        int i = 0;
        for (int j = 0; i < m && j < n; ++j) {
            if (s.charAt(i) == t.charAt(j)) {
                ++i;
            }
        }
        return i == m;
    }
}

复杂度

面试官可能追问