Leetcode 【583、809、816】
Leetcode 【583、809、816】
题目描述：【DP】583. Delete Operation for Two Strings
解题思路：
这道题目是给两个单词 word1 和 word2，每次只能从中删除一个字符，最后两单词相等，求最少删除次数。
两个单词通过删除某些字符最后相等，而且要求删除次数最少，很明显最后相等的单词是两个原来单词的最长公共子序列。因此，这道题变成了求解两单词的最长公共子序列问题。因为一次只能删除一个字符，因此 len(word1) + len(word2) - 2 * (最长公共子序列的长度) 就是最后的答案。
使用动态规划来求解最长公共子序列问题，时间复杂度和空间复杂度均为 O(n^2)。
Python3 实现：
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
dp = [[0] * (len(word2) + 1) for _ in range(len(word1) + 1)]
for i in range(1, len(word1) + 1):
for j in range(1, len(word2) + 1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return len(word1) + len(word2) - 2 * dp[-1][-1]题目描述：【String】809. Expressive Words
解题思路：
这道题是给一个字符串S和一个单词数组，S是数组中的单词通过重复某些字符至少三次得到的，找到符合的单词。
注意：如 S = "helllo"，那么 "helo"、"hello"、"helllo" 这些单词都是符合 S 的。
刚开始的做法是将 S 按照相同的字符进行分割，得到索引和相同字符长度的对应字典，如 S = "heeellllo" 可以得到 dic = { 0: 1, 1: 3, 4: 4, 8:1}。然后，对于字典中的每个单词 word ，判断对应位置的字符是否符合 S，不过有很多细节情况需要注意，下面以 S = "heelllo" （dic = {0: 1, 1: 2, 3: 3, 6: 1}），word = "heello" 为例：
- i 指向 S，j 指向 word；
- 前三个字符都对应，则 i 和 j 每次后移一位；如果不对应，标记为 False 终止判断；
- S[3] 和 word[3] 相等，i 在 dic 中且 dic[3] >= 3，则 i 直接后移 3 位到 o 的位置，word 要判断 word[3] 后重复的 l 有几个。如果不大于 3 个，则满足，并且也移动到 o 的位置，继续和 S 中的 o 判断；如果超过 3 个，标记为 False 终止判断；
- 到最后，满足 S 的单词一定是遍历完了所有的 S 和 word 字符，并且没有被标记过 False。
具体看代码（虽然代码很长，但是还算比较好理解）。
Python3 实现：
class Solution:
def expressiveWords(self, S: str, words: List[str]) -> int:
ans = 0
dic = dict() # 按相同字符切割S {起始索引：重复字符长度}
cnt = 1
for i in range(len(S) - 1):
if S[i] == S[i+1]:
cnt += 1
else:
dic[i-cnt+1] = cnt
cnt = 1
dic[i-cnt+2] = cnt
for word in words: # 对于每个字符
i = j = 0 # i指向S，j指向word
while i < len(S) and j < len(word):
flag = True
if S[i] == word[j]:
if i in dic and dic[i] >= 3:
tem = dic[i]
i += tem # i向后移动tem位到下一个不相同的字符处
cnt = 1
while j < len(word) - 1: # 统计word中当前字符重复的次数
if word[j] == word[j+1]:
cnt += 1
j += 1
else:
break
j += 1 # word移动到下一个不相同的字符处
if cnt > tem: # word中当前字符重复次数比S对应字符还要多，不满足，终止判断
flag = False
break
else: # 不满足重复3次的条件，各向后移动1位继续判断
i += 1
j += 1
else: # S和word对应字符不相等，不满足，终止判断
break
if i == len(S) and j == len(word) and flag: # 最终满足的条件
ans += 1
return ans写完后，看了一下其他人的解题思路，发现一种更精妙的解题方法：首先把 S 做分割，把每个单词 word 也做分割，保存在列表中；然后，判断S的分割能否被 word 的分割一一对应上。
- 如果两个列表长度不对应，说明不满足题意，终止判断；
- 如果对应字符不相等或者word中某字符的长度大于S对应字符的长度，说明不满足题意，终止判断；
- 如果word中某字符的长度等于S对应字符的长度，继续判断；
- 如果S某字符长度小于 3，说明不满足题意，终止判断。
最后，留下来的都是满足题意的。
将字符串的分割可以利用 Python 的 itertools 中的 groupby 函数，用法是：
base = [(x[0], len(list(x[1]))) for x in groupby("heeellllooo")]，将会得到：
[('h', 1), ('e', 3), ('l', 4), ('o', 3)]Python3 实现：
from itertools import groupby
class Solution:
def expressiveWords(self, S: str, words) -> int:
base = [(x[0], len(list(x[1]))) for x in groupby(S)]
def valid(w):
curr = [(x[0], len(list(x[1]))) for x in groupby(w)]
if len(curr) != len(base): return False # 长度不同
for (c1, cnt1), (c2, cnt2) in zip(base, curr): # zip函数按照对应项分配
if c1 != c2 or cnt2 > cnt1: return False
if cnt1 == cnt2: continue
if cnt1 < 3: return False
return True
return len([w for w in words if valid(w)])
print(Solution().expressiveWords("helllo", ["hello", "helo", "hi"])) # 2题目描述：【String】816. Ambiguous Coordinates
解题思路：
这道题是给一个字符串 S，通过用逗号和小数点将 S 分割为两部分，得到不同的组合坐标 (x, y)，要求 x、y 中的数字都是合法的，返回所有合法坐标。
这道题的做法很朴素，可以先保存所有的分割情况到列表中，其中包括非法的坐标，然后再将非法的坐标从列表中删除即可。编程时要注意考虑到所有非法的情况。
Python3 实现：
class Solution:
def ambiguousCoordinates(self, S: str) -> List[str]:
ans = []
# 先保存所有的组合情况，包括非法项
for i in range(1, len(S) - 2):
le, ri = S[1:i+1], S[i+1:-1] # 划分S为两部分
for j in range(len(le)): # 左边组合情况
if len(le[j+1:]) != 0:
le2 = le[:j+1] + "." + le[j+1:]
else:
le2 = le[:j+1]
for k in range(len(ri)): # 右边组合情况
if len(ri[k+1:]) != 0:
ri2 = ri[:k+1] + "." + ri[k+1:]
else:
ri2 = ri[:k+1]
ans.append([le2, ri2])
# 把非法的项删除
i = 0
while i < len(ans):
# 非法的整数部分：整数部分长度大于2且以0开头，如 001、023.01
if len(ans[i][0].split(".")[0]) > 1 and ans[i][0][0] == "0":
del ans[i]
elif len(ans[i][1].split(".")[0]) > 1 and ans[i][1][0] == "0":
del ans[i]
# 非法的小数部分：小数部分最后以0结尾，如 0.0、3.20、0.010
elif ans[i][0].find(".") >= 1 and ans[i][0][-1] == "0":
del ans[i]
elif ans[i][1].find(".") >= 1 and ans[i][1][-1] == "0":
del ans[i]
else:
i += 1
# 输出结果，不包括非法项
ret = []
for a in ans:
ret.append('(' + a[0] + ", " + a[1] + ')')
return ret