难度: Medium
给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
示例 1：
输入: word1 = "sea", word2 = "eat" 输出: 2 解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"
示例 2:
输入：word1 = "leetcode", word2 = "etco" 输出：4
提示：
1 <= word1.length, word2.length <= 500word1 和 word2 只包含小写英文字母运行时间: 55 ms
内存: 16.0 MB
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
idx = defaultdict(list)
for i, c in enumerate(word2):
idx[c].append(i)
tail = deque()
for c in word1[::-1]:
for i in idx[c]:
j = bisect_right(tail, i)
if j == 0:
tail.appendleft(i)
else:
tail[j - 1] = i
return len(word1) + len(word2) - 2 * len(tail)
这个题解使用了最长公共子序列 (LCS) 的思路。主要步骤如下： 1. 先遍历 word2，用一个哈希表 idx 记录每个字符在 word2 中出现的所有位置。 2. 逆序遍历 word1，对于每个字符，在 idx 中找到它在 word2 中出现的位置。 3. 使用一个双端队列 tail 维护一个单调递增的序列，表示 LCS 在 word2 中的下标。对于每个位置，用二分查找在 tail 中找到第一个大于等于它的位置 j，如果 j 为 0 就插入到队首，否则替换 tail[j-1]。 4. 最后 tail 的长度就是 LCS 的长度，用两个单词的长度之和减去 2 倍的 LCS 长度即可得到删除操作的最小步数。
时间复杂度: 平均情况下的时间复杂度是 O(m * k_avg * log(min(m, n)))，其中 k_avg 是字符在 word2 中的平均出现次数。最坏情况下的时间复杂度是 O(mn/c * log(min(m, n)))，其中 c 是字符集的大小。
空间复杂度: 空间复杂度是 O(n)。
```python
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
# 记录 word2 中每个字符出现的位置
idx = defaultdict(list)
for i, c in enumerate(word2):
idx[c].append(i)
# 维护 LCS 在 word2 中的下标
tail = deque()
for c in word1[::-1]:
for i in idx[c]:
# 二分查找第一个大于等于 i 的位置 j
j = bisect_right(tail, i)
if j == 0:
# 如果 j 为 0，插入到队首
tail.appendleft(i)
else:
# 否则替换 tail[j-1]
tail[j - 1] = i
# 两个单词的长度之和减去 2 倍的 LCS 长度
return len(word1) + len(word2) - 2 * len(tail)
```
从后向前遍历 word1 的目的是为了方便地维护 tail 队列中下标的单调递增性。如果从前向后遍历，每次插入新的下标到 tail 时，可能需要更复杂的操作来保证序列的单调性，因为新的下标可能小于已存在的某些下标。从后向前遍历可以保证插入的下标总是尽可能小，使得后续的下标更容易满足单调递增的条件，简化了维护过程。
当字符分布非常不均匀时，如某个字符在 word2 中频繁出现，那么哈希表中这个字符对应的列表会变得很长。这将导致在 word1 中对应字符的处理时，需要遍历这个较长的列表，从而增加了处理时间。此外，大量的重复字符下标存储还会增加空间复杂度。因此，在字符极端不均匀分布的情况下，这种方法的性能和空间使用都可能受到负面影响。
在题解的算法中，通过二分查找确保了每次替换操作都正确维护了 tail 的单调递增性。二分查找找到的位置 j 是第一个大于等于当前下标 i 的位置，替换操作只会发生在 tail[j-1] = i，这确保了替换后 tail 仍然是单调递增的。因为 i 是从 word1 中从后向前遍历得到的，保证了每次替换都是用更小的或相等的下标替换前一个元素，不会破坏队列的单调性。
二分查找在 tail 中寻找第一个大于等于当前下标 i 的元素位置 j。如果 tail 中所有元素都小于 i，那么 j 将是 tail 的长度，表示 i 应该添加到 tail 的末尾。如果 j 是 0，表示当前下标 i 小于或等于 tail 中所有元素，应插入到队首。如果 0 < j < tail 的长度，表示找到了一个位置，其前一个元素小于 i，而位置 j 的元素大于等于 i，因此应将 tail[j-1] 替换为 i，以维持单调递增性。这个操作保证了无论是插入还是替换，tail 队列始终维持单调递增的状态。