LeetCode 555. 分割连接字符串
题目描述
题意分析
每个字符串可以保持原样或整体反转，但各字符串仍要按原数组顺序连接成环。再任选一个字符作为剪开后的起点，沿环读完全部字符，求所有结果中字典序最大的字符串。
如果直接枚举所有字符串的朝向，选择数会指数增长。固定剪点后，只有剪点所在的字符串被拆成首尾两段，其余字符串都作为完整块出现，可以分别选择较大的朝向，只对被剪开的那一块枚举。
解法：贪心 + 枚举
核心思路
[!blue]
枚举唯一被剪开的字符串，其余字符串独立选较大朝向。 对一个完整块，原串和反串长度相同；其他位置不变时，换成字典序较大的朝向不会改变前面的字符或后面块的位置，整串的第一个差异也只会使结果变大。因此所有完整块都可以独立贪心，预处理为各自较大的朝向。剪点块的前后缀会被分开，原来靠后的字符可能变成整个结果的开头，不能只按未切分时的整块大小决定朝向。枚举它的下标
i，再分别尝试当前字符串和其反转；即使预处理改过它，这两种形态仍恰好覆盖原串与反串。令本次朝向为
cur，剪点为j，候选顺序固定为：cur[j:]，原数组中i后面的全部块，i前面的全部块，最后是cur[:j]。这样从剪点沿原环走一圈，每个字符恰好使用一次，也没有改变块的循环顺序。每个合法结果都能找到对应的
i、朝向和j，而它的其他完整块又都可替换为贪心朝向而不变差，因此枚举中的最大值就是全局最优。j取零覆盖块之间的接缝；不需要取cur.length()，因为那等价于下一块的起点。只有一个字符串时，中间两组块为空，同样是在枚举它的两种朝向及所有循环起点。
解题步骤
- 将每个字符串替换为自身与反转中的较大者。
- 枚举剪点所在字符串的两种朝向。
- 枚举剪点，从该点沿原环顺序拼出完整候选。
- 保留字典序最大结果。
代码实现
class Solution {
public String splitLoopedString(String[] strs) {
int n = strs.length;
// 非剪点串在结果里是独立的连续块，各自取最大形态即为最优。
for (int i = 0; i < n; i++) {
String rev = new StringBuilder(strs[i]).reverse().toString();
if (rev.compareTo(strs[i]) > 0) {
strs[i] = rev;
}
}
String answer = "";
// 枚举哪个串被剪开。
for (int i = 0; i < n; i++) {
String rev = new StringBuilder(strs[i]).reverse().toString();
// 剪点串会被拆成头尾两段，两种朝向都必须试。
for (String cur : new String[] {
strs[i],
rev
}) {
for (int j = 0; j < cur.length(); j++) {
StringBuilder sb = new StringBuilder();
sb.append(cur.substring(j));
// 从剪点出发沿环走一圈：先绕到末尾，再从头接回来。
for (int k = i + 1; k < n; k++) {
sb.append(strs[k]);
}
for (int k = 0; k < i; k++) {
sb.append(strs[k]);
}
sb.append(cur.substring(0, j));
String candidate = sb.toString();
if (candidate.compareTo(answer) > 0) {
answer = candidate;
}
}
}
}
return answer;
}
}
import "strings"
func splitLoopedString(strs []string) string {
n := len(strs)
// 非剪点串在结果里是独立的连续块，各自取最大形态即为最优。
for i := 0; i < n; i++ {
rev := reverse(strs[i])
if rev > strs[i] {
strs[i] = rev
}
}
answer := ""
// 枚举哪个串被剪开。
for i := 0; i < n; i++ {
rev := reverse(strs[i])
// 剪点串会被拆成头尾两段，两种朝向都必须试。
for _, cur := range []string{
strs[i],
rev,
} {
for j := 0; j < len(cur); j++ {
var sb strings.Builder
sb.WriteString(cur[j:])
// 从剪点出发沿环走一圈：先绕到末尾，再从头接回来。
for k := i + 1; k < n; k++ {
sb.WriteString(strs[k])
}
for k := 0; k < i; k++ {
sb.WriteString(strs[k])
}
sb.WriteString(cur[:j])
if candidate := sb.String(); candidate > answer {
answer = candidate
}
}
}
}
return answer
}
func reverse(s string) string {
b := []byte(s)
for i, j := 0, len(b)-1; i < j; i, j = i+1, j-1 {
b[i], b[j] = b[j], b[i]
}
return string(b)
}
复杂度分析
- 时间复杂度：$O(M^2)$，$M$ 为总字符数。两种朝向下总共枚举 $2M$ 个起点，每个候选的构造和字典序比较最多需要 $O(M)$。
- 空间复杂度：$O(M)$，保存朝向调整与候选字符串，输入数组会被改写。
关键点总结
[!green]
- 完整块的朝向可独立贪心，剪点块必须枚举。
- 数组循环顺序固定，不能重排各字符串。
- 候选总长度始终等于所有字符串总长度。
易错点总结
[!yellow]
- 剪点块也只用预处理后的朝向：可能漏掉更优旋转。
- 中间块直接按从零开始的顺序拼接：破坏从剪点沿环行走的顺序。
- 只在字符串接缝处剪：漏掉内部切点。
- 按长度比较候选：所有合法候选长度相同，应比较字典序。
- 题目只含小写英文字母，Go 按字节反转与比较就符合字符顺序；代码会原地替换输入数组中的字符串朝向。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1163. 按字典序排在最后的子串 | 困难 | 同样比较字典序最大的后缀或切分起点，本题还要选择各段是否反转并考虑首尾连接。 |
| 899. 有序队列 | 困难 | 同样涉及循环切分，原题k=1时只是整串旋转，本题还允许独立翻转每个原字符串。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！