What is the two-pointer approach in the context of the Longest Word in Dictionary through Deleting problem?

In this problem, the two-pointer approach involves using one pointer to traverse the string `s` and another pointer to track each dictionary word, checking if characters can be deleted to form the word.

How can I optimize the solution for the problem 'Longest Word in Dictionary through Deleting'?

You can optimize by using early termination when you find the longest valid word or by eliminating unnecessary checks for words that are shorter than the current longest valid word.

What are common mistakes when solving 'Longest Word in Dictionary through Deleting'?

Common mistakes include neglecting lexicographical order, inefficient scanning with nested loops, and not handling edge cases where no words can be formed.

How does lexicographical order affect the solution to this problem?

If multiple words can be formed from `s`, lexicographical order is used to return the smallest one. This ensures that among equally long valid words, the word that appears first alphabetically is returned.

Can the two-pointer approach be applied to other string-related problems?

Yes, the two-pointer approach is widely used for problems involving string matching, subsequences, or partitions, where elements need to be compared or scanned in parallel.

#524

Medium

auto_awesome双·指针·invariant

LeetCode 题解工作台

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

给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。示例 1：输入： s = "abpcplea", di…

数组双指针字符串排序

题目描述

给你一个字符串 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] 仅由小写英文字母组成

lightbulb

解题思路

方法一：判断子序列

我们定义一个函数 $check(s, t)$ ，用于判断字符串 $s$ 是否是字符串 $t$ 的子序列。我们可以使用双指针的方法，初始化两个指针 $i$ 和 $j$ 分别指向字符串 $s$ 和字符串 $t$ 的开头，然后不断移动指针 $j$ ，如果 $s[i]$ 和 $t[j]$ 相等，则移动指针 $i$ ，最后判断 $i$ 是否等于 $s$ 的长度即可。若 $i$ 等于 $s$ 的长度，则说明 $s$ 是 $t$ 的子序列。

我们初始化答案字符串 $ans$ 为空字符串，然后遍历数组 $dictionary$ 中的每个字符串 $t$ ，如果 $t$ 是 $s$ 的子序列，并且 $t$ 的长度大于 $ans$ 的长度，或者 $t$ 的长度等于 $ans$ 的长度且 $t$ 字典序小于 $ans$ ，则更新 $ans$ 为 $t$ 。

时间复杂度 $O(d \times (m + n))$ ，其中 $d$ 是字符串列表的长度，而 $m$ 和 $n$ 分别是字符串 $s$ 的长度和字符串列表中字符串的平均长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate effectively uses two-pointer scanning to match characters between `s` and dictionary words.
question_mark
Look for optimization strategies, especially how they handle lexicographical order and early termination.
question_mark
Assess how the candidate handles edge cases, such as when no words can be formed from `s`.

warning

常见陷阱

外企场景

error
Failing to account for lexicographical order when multiple words of the same length are valid.
error
Not using the two-pointer method efficiently, leading to unnecessary scans of `s`.
error
Overcomplicating the problem with excessive nested loops instead of leveraging simple pointer movement.

swap_horiz

进阶变体

外企场景

arrow_right_alt
The problem could be extended to handle uppercase letters or include non-English characters in the string and dictionary.
arrow_right_alt
A variant could involve finding the second longest valid word if the longest one has multiple occurrences.
arrow_right_alt
The task might be modified to allow for insertion or replacement of characters instead of only deletions.

help

常见问题

外企场景

继续练习

#522 最长特殊序列 II #1048 最长字符串链 #532 数组中的 k-diff 数对