这道题是给一个词典和句子,词典中保存着词根,将句子中的所有继承词(在词根后面加字符)用对应词根替换掉。如果继承词有许多可以形成它的词根,则用最短的词根替换它。
因为句子中的单词数 <= 1000 并且每个单词长度 <= 1000,因此可以对句子中的每个单词 word 的每个字符 ch 进行遍历,并且用一个变量 pre 记录单词 word 的前缀。如果 pre 在词典中能找到(为加快查找速度,可以将词典转化为 set),说明以 pre 为前缀的 word 可以用词典中的对应词根替换掉。如果 pre 在词典中都不能找到,则不替换即可。
如果句子中单词数为 m,单词长度为 n,则时间复杂度为 O(m*n)。
class Solution:
def replaceWords(self, dict: List[str], sentence: str) -> str:
ans = []
setd = set(dict) # 转化为集合,使得查找为O(1)
for word in sentence.split(" "): # 按照空格划分句子中的单词
pre = "" # 记录单词前缀
flag = False
for ch in word:
pre += ch # 记录word前缀
if pre in setd: # 如果word前缀在集合中
ans.append(pre)
flag = True
break
if not flag: # 没有在集合中找到该单词的根
ans.append(word)
return " ".join(ans)
这道题是给一个01矩阵,通过翻转列使得相等的行数(一行全0或全1)最多。
基于上述分析,可以直接用 Hash Table 统计行的种类有多少个,找到行的种类数最多的就是答案。
举例,matrix = [[0,0,0],[0,0,1],[1,1,0]]
如果矩阵为 m*n,则时间复杂度为 O(m*n),空间复杂度为 O(k*n),k 为行种类的个数。
class Solution:
def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
dic = collections.defaultdict(int) # 统计不同行的种类的个数
for row in matrix:
if row[0] == 0:
dic[tuple([col for col in row])] += 1
elif row[0] == 1: # 如果某一行以1开头,则先按位取反,再加入到dic中
dic[tuple([1-col for col in row])] += 1
return max(dic.values())