这道题目是给两个单词 word1 和 word2,每次只能从中删除一个字符,最后两单词相等,求最少删除次数。
两个单词通过删除某些字符最后相等,而且要求删除次数最少,很明显最后相等的单词是两个原来单词的最长公共子序列。因此,这道题变成了求解两单词的最长公共子序列问题。因为一次只能删除一个字符,因此 len(word1) + len(word2) - 2 * (最长公共子序列的长度)
就是最后的答案。
使用动态规划来求解最长公共子序列问题,时间复杂度和空间复杂度均为 O(n^2)。
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]
这道题是给一个字符串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" 为例:
具体看代码(虽然代码很长,但是还算比较好理解)。
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 的分割一一对应上。
最后,留下来的都是满足题意的。
将字符串的分割可以利用 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
这道题是给一个字符串 S,通过用逗号和小数点将 S 分割为两部分,得到不同的组合坐标 (x, y),要求 x、y 中的数字都是合法的,返回所有合法坐标。
这道题的做法很朴素,可以先保存所有的分割情况到列表中,其中包括非法的坐标,然后再将非法的坐标从列表中删除即可。编程时要注意考虑到所有非法的情况。
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