难度: Medium
Submission
运行时间: 47 ms
内存: 16.1 MB
class Solution:
def splitLoopedString(self, strs: List[str]) -> str:
# 最关键的信息：1 <= sum(strs[i].length) <= 1000
# 只要们确定了取某一个字符作为起点，其它字符串比如是取字典序最大的
ans = ''.join(strs)
mx = [max(s, s[::-1]) for s in strs]
t = max(ans)
for i, s in enumerate(strs):
if t not in s:
continue
res = ''.join(mx[i+1:] + mx[:i])
for j, c in enumerate(s):
if c == t:
p = s[j:] + res + s[:j]
ans = max(ans, p)
s1 = s[::-1]
for j, c in enumerate(s1):
if c == t:
p = s1[j:] + res + s1[:j]
ans = max(ans, p)
return ans
Explain
该题解的思路是枚举所有可能的起点，对于每个起点，将其它字符串取字典序最大的字符串拼接起来，形成一个候选答案。最后从所有候选答案中取字典序最大的作为最终答案。具体来说： 1. 先计算出每个字符串及其反转后的字典序最大值，存入数组 mx 中。 2. 枚举每个字符串 s 作为起点字符串： - 如果 s 中不包含当前最大字符 t，则跳过该字符串。 - 将 mx 数组中除了 s 对应位置以外的字符串拼接起来，得到 res。 - 枚举 s 的每个字符作为起点，将 s 从该字符划分为两部分，与 res 拼接，更新答案。 - 同样枚举 s 反转后的每个字符作为起点，重复上述过程。 3. 返回所有候选答案中字典序最大的字符串。
时间复杂度: O(m^2/n)，其中 n 为字符串数组的长度，m 为所有字符串的总长度。
空间复杂度: O(n + m)，其中 n 为字符串数组的长度，m 为所有字符串的总长度。
```python
class Solution:
def splitLoopedString(self, strs: List[str]) -> str:
# 最关键的信息：1 <= sum(strs[i].length) <= 1000
# 只要们确定了取某一个字符作为起点，其它字符串比如是取字典序最大的
ans = ''.join(strs)
# 计算每个字符串及其反转后的字典序最大值
mx = [max(s, s[::-1]) for s in strs]
t = max(ans)
# 枚举每个字符串作为起点字符串
for i, s in enumerate(strs):
# 如果当前字符串中不包含最大字符，则跳过
if t not in s:
continue
# 拼接除当前字符串外的其它字符串的字典序最大值
res = ''.join(mx[i+1:] + mx[:i])
# 枚举当前字符串的每个字符作为起点
for j, c in enumerate(s):
if c == t:
p = s[j:] + res + s[:j]
ans = max(ans, p)
# 枚举当前字符串反转后的每个字符作为起点
s1 = s[::-1]
for j, c in enumerate(s1):
if c == t:
p = s1[j:] + res + s1[:j]
ans = max(ans, p)
return ans
```
Explore
这一步的优势在于能够在构建答案串的过程中始终保持尽可能大的字典序。对于每个字符串，其正序和反序中必有一个字典序较大，故预先计算并存储每个字符串及其反转后的最大字典序，可以在后续的拼接操作中直接使用这些最大字典序字符串，避免了每次选择时重新计算，从而提高算法效率并简化逻辑。
这种策略的合理性在于尝试构建以最大字符 t 开头的最大字典序字符串。如果一个字符串不包含最大字符 t，那么从该字符串任何位置开始，都不可能构造出以 t 为首的字典序最大字符串。因此，跳过这些不包含 t 的字符串可以减少无效的枚举，提高算法效率。该策略不会错过最优解，因为最优解必然是以字典序中的最大字符开头。
此方法是正确的。因为 ans 是初始的字符串拼接结果，包含了所有字符，包括每个字符串的所有字符。因此，在 ans 中计算出的最大字符 t 确实是整个字符串集合中字典序最大的字符。使用这个字符作为参照来构建可能的最大字典序解是合理的。
尽管 s 的正序和反序都被考虑在内，但是每次构建新的候选答案时，我们需要确保从字典序最大的字符 t 开始，无论是正序还是反序。这是因为，我们的目标是构建字典序最大的字符串，因此仅当枚举到的字符是 t 时，才会进行拼接和比较。这样可以保证无论是从 s 的正序还是反序开始，都是以最大可能的字典序构建字符串。