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

从 s 删掉几个字母，够到字典里哪个词

给一个字符串 s 和一串候选词 dictionary，问：把 s 里某些字母删掉、剩下的保持原来的先后顺序，能拼出字典里哪个词，要最长的那个；多个一样长就取字典序最小的，都够不到就返回空串。题面例子 s="abpcplea"、dictionary=["ale","apple","monkey","plea"]，答案 "apple"。

把 s 所有删法都列出来，为什么行不通

很自然会想到把 s 的所有删法穷举出来：s 长 n，每个字母删或不删两种选择，共 2^n 种结果，n 到 20 就是一百多万条，再和字典比对撑不住。换个方向：不列 s 能变成什么，而是拿字典每个词，直接问它能不能由 s 删字母得到。

「删字母能得到 word」翻成一句什么话

把 s 删几个字母得到 word，等价于说 word 是 s 的子序列——word 的每个字母都能在 s 里按先后顺序对上，中间隔多远都行，但次序不能乱。判子序列有个标准双指针写法：i 指 word 当前要找的字母、j 从头扫 s，s[j] 和 word[i] 相等就算对上一个、i 往后挪一位，不管相不相等 j 每轮都右移。等 i 走到 word 末尾，说明每个字母都按顺序找齐，word 就是子序列。

方向别弄反：i 走候选词 word、j 走源串 s，因为是从 s 里删字母得到 word；也只在相等时推进 i，光看字母都在 s 里出现过不够，次序乱了照样删不出来。

一个词判完是子序列，接下来比什么

判定只解决单个词，外面还要挑答案。遍历字典每个候选，判是不是子序列；是的话再和手里存的最优比：更长就替换，一样长就比字典序、更小才替换。全部试完，手里剩的就是最长且字典序最小的。别碰到第一个子序列就返回——后面可能有更长的，或同样长却更靠前的。

abpcplea 配四个候选，apple 怎么胜出

ale：找 a，第 0 位对上、i 到 1；找 l 跳过 b、p、c、p，第 5 位对上、i 到 2；找 e，第 6 位对上、i 到 3 走完，是子序列，比空答案长，先存 ale。

apple：a 对上第 0 位，p 跳过 b 对上第 2 位，第二个 p 跳过 c 对上第 4 位，l 对上第 5 位，e 对上第 6 位，i 走完 5 个字母，是子序列且比 ale 长，答案换 apple。monkey：首字母 m 扫遍 s 都没有，i 卡在 0，淘汰。

plea：p 跳过 a、b 对上第 2 位，l 对第 5 位，e 对第 6 位，a 对第 7 位，i 走完 4 个字母，也是子序列——但只有 4 个，没比存着的 apple（5 个）长，答案不变。四个试完，apple 胜出。

全军覆没、同长打平，这些角落别漏

复杂度上，设 s 长 n、字典 d 个词，每个候选双指针扫一遍 s 是 O(n)，合计 O(d·n)；只用两个指针加一个答案串，额外空间 O(1)。

几个角落容易漏。没有一个词是子序列时，答案是初始空串，记得给初值。两个候选一样长又都合格，得按字典序取小，返回先遇到的会错。比 s 还长的候选，i 走不到末尾，自然判成非子序列，不必先比长度。

Python

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

C++

#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;
    }
};

Java

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;
    }
}