Leetcode 3474. Lexicographically Smallest Generated String

• Leetcode 3474. Lexicographically Smallest Generated String
  
  
  
  • 1. 解题思绪
    
  • 2. 代码实现
    
  
  

  

• 标题链接：3474. Lexicographically Smallest Generated String
  

1. 解题思绪

这一题思绪上主要就是分成两步：

• 找到所有为T的位置，此时其对应的位置及厥后续m-1个字符必然就是str2
  
• 在所有未填的字符当中填入其他字符使其在满足条件的情况下字典序最小
  

此中，有关第一步，我们需要保证我们在填入本身的合法性，因此我们需要在填入位置重叠的情况下判断填入的合法性，即交织的部门必须完全一致，此时我们就是要判断对应位置的子串是否与头部位置的子串完全重合。这个我们可以轻松地通过z算法进行实现，对应的内容可以参考拙作《经典算法：Z算法（z algorithm）》，这里我们就不外度展开了。
别的，关于第二步，我们只需要考察在每一个未填的位置可以填入最小字符a即可，这样，我们就可以确保对应的字符串合法且字典序最小。
而要判断某个位置是否可以填入某个字符，这里我做的比力暴力，即考察包罗其本身的前m个字符分别作为开头时是否刚好有某个子串恰恰为str2，如果没有就是合法的，反之就必然不合法。
最后需要注意的是，我们还需要考察一下每一个F地点的位置对应的子串是否真的都不合法，它有时会和第一步产生矛盾，此时我们需要去掉对应的情况。
2. 代码实现

给出python代码实现如下：

1. def z_algorithm(s):
2.     n = len(s)
3.     z = [0 for _ in range(n)]
4.     l, r = -1, -1
5.     for i in range(1, n):
6.         if i > r:
7.             l, r = i, i
8.             while r < n and s[r-l] == s[r]:
9.                 r += 1
10.             z[i] = r-l
11.             r -= 1
12.         else:
13.             k = i - l
14.             if z[k] < r - i + 1:
15.                 z[i] = z[k]
16.             else:
17.                 l = i
18.                 while r < n and s[r-l] == s[r]:
19.                     r += 1
20.                 z[i] = r-l
21.                 r -= 1
22.     z[0] = n
23.     return z
25. class Solution:
26.     def generateString(self, str1: str, str2: str) -> str:
27.         n, m = len(str1), len(str2)
28.         z = z_algorithm(str2 + str2)[m:]
29.         
30.         ans = ["" for _ in range(n+m-1)]
31.         nxtT = n
32.         for i in range(n-1, -1, -1):
33.             ch = str1[i]
34.             if ch == "T":
35.                 if nxtT == n or nxtT-i >= m:
36.                     for j in range(i, i+m):
37.                         ans[j] = str2[j-i]
38.                 elif z[nxtT-i] >= m-(nxtT-i):
39.                     for j in range(i, nxtT):
40.                         ans[j] = str2[j-i]
41.                 else:
42.                     return ""
43.                 nxtT = i
44.                
45.         def is_allowed(idx, ch):
46.             lb = max(idx-m+1, 0)
47.             rb = min(n-1, idx)
48.             
49.             def is_not_same(i):
50.                 return str2[idx-i] != ch or any(ans[i+j] != str2[j] for j in range(m) if i+j != idx)
51.             
52.             return all(is_not_same(i) for i in range(lb, rb+1))
54.         prefix = str2[:-1]
55.         for i in range(n+m-1):
56.             if ans[i] != "":
57.                 if i < n and str1[i] == "F" and all(ans[i+j] == str2[j] for j in range(m)):
58.                     return ""
59.                 continue
60.             for ch in string.ascii_lowercase:
61.                 if is_allowed(i, ch):
62.                     ans[i] = ch
63.                     break
64.         return "".join(ans)

复制代码

提交代码评测得到：耗时2665ms，占用内存18.4MB。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。