LeetCode 555. 分割连接字符串

2021-09-17 HGNULB 约 11 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 555. 分割连接字符串

题意分析

给一组字符串 strs。每个字符串都可以选择保持原样或整体反转，然后按给定的顺序首尾相接、并把末尾接回开头，围成一个环。接着在环上任选一个位置剪开，得到一个线性字符串。问所有可能的「反转方案 × 剪开位置」组合里，字典序最大的结果是什么。

有三处必须先读准。第一，数组的顺序是固定的，只能决定每个串的朝向，不能重排。第二，反转是对整个串做的，不是对某个片段。第三，剪开位置可以落在任意两个字符之间，包括某个串的内部——这一点是全题的关键，如果只能在串与串的接缝处剪，问题会简单得多。

剪开位置的自由度带来了一个重要推论：剪点所在的那个串会被拆成两半，前半跑到结果末尾、后半跑到结果开头。于是所有串被天然分成两类——唯一那个被剪开的串，和其余保持完整的串。这两类的处理方式完全不同，是设计算法的分界线。

数据规模上，串的数量和总长度都不大（总字符数是百级），环上剪点数等于总长度，每个候选结果的构造和比较都是线性的，说明 $O(m^2)$（m 为总长度）这一量级完全可以接受。题目没有暗示什么精妙的线性算法，反而暗示「把所有剪点老老实实枚举一遍」是被期待的主干。

边界：只有一个串时，环就是这个串自己，答案是它（或它的反转）的所有旋转里最大的那个；剪点取在下标 0 时相当于不拆，前半是空串；结果长度恒等于所有串长度之和，与选哪种方案无关。

解法：贪心 + 枚举

核心思路

先估暴力：每个串两种朝向，n 个串就是 $2^n$ 种组合，再乘上 m 个剪点，总共 $2^n \cdot m$ 个候选。n 稍大就不可行。必须把这个指数砍掉。

砍掉它的观察在于两类串的角色不对称。对于没有被剪开的串，它在最终结果中是以一个完整的、连续的块出现的，而且它左右两侧的内容与它自身的朝向无关。字典序比较是逐位从左往右进行的，在其他部分完全固定的前提下，把这个块换成字典序更大的版本，整个结果只会变大不会变小。所以对每个非剪点串，独立地取 max(s, reverse(s)) 就是最优的，根本不需要枚举——这一步把 $2^n$ 压成了 $O(1)$ 的贪心决策。

而被剪开的那个串不能这样贪。它被拆成了两段并分别放在结果的头和尾，反转它会同时改变「哪些字符跑到开头」和「它们的排列顺序」，与「整串谁更大」不是一回事。举个直观的例子：串 "ba" 本身比 "ab" 大，但若剪点让后半跑到开头，用 "ab" 时开头是 "b"，用 "ba" 时开头可能是 "a"，结论完全反过来。所以对剪点串必须两种朝向都试。

于是算法定型为两阶段。预处理阶段：把每个 strs[i] 就地替换成 max(strs[i], reverse(strs[i]))，此后它们就是「作为完整块出现时的最优形态」。枚举阶段：依次假设第 i 个串是被剪开的那个，对它的两种朝向 cur、以及它内部的每个剪点 j，拼出候选串

cur[j..] + strs[i+1] + ... + strs[n-1] + strs[0] + ... + strs[i-1] + cur[..j]

取所有候选中字典序最大的即为答案。注意中间那串「其余字符串」的拼接顺序：从 i + 1 绕到末尾，再从 0 绕回 i - 1——这正是「在环上从剪点出发走一圈」的顺序，写错顺序等于换了一个环。

这里的不变量是：枚举阶段读取的 strs[k]（k != i）永远是预处理后的最优形态，而剪点串的朝向由 cur 单独控制、不受预处理结果约束。之所以对剪点串仍从预处理后的值出发再取反转，是因为「一个串和它的反转」这个二元集合在反转操作下封闭——预处理把哪一个留在数组里都不影响这两种朝向都被枚举到。

解题步骤

第一遍循环：把每个 strs[i] 替换成它与自身反转中字典序较大的那个。为什么：非剪点串在结果里是一个独立的连续块，四周的内容与它的朝向无关，因此逐位比较下「块更大 ⇒ 整体不更小」，可以各自独立取最优；这一步把 $2^n$ 的朝向枚举彻底消掉。

准备答案变量 answer = ""。为什么：空串是字典序最小的，任何合法候选都能赢过它，省掉「第一次特殊处理」的分支。

外层循环枚举哪个串 i 被剪开。为什么：剪点只能落在某一个串里，按串分组枚举可以让「其余串怎么拼」在整个内层保持固定的规律。

内层先枚举 cur 取 strs[i] 和它的反转两种朝向。为什么：剪点串会被拆成头尾两段，反转会同时改变「哪半跑到开头」和「字符顺序」，不能沿用非剪点串的贪心结论，必须两种都试。从预处理后的值再反转不会漏解，因为这两种朝向恰好就是原串的两种朝向。

再枚举剪点 j 从 0 到 cur.length() - 1。为什么：j 表示「从下标 j 处剪开」，cur[j..] 成为结果开头、cur[..j] 成为结果结尾；j = 0 表示恰好在这个串的最前面剪，此时它整块出现在开头、尾段为空——这个情形必须包含在内，否则「在接缝处剪」的方案会被漏掉。

按 cur[j..] → strs[i+1..n-1] → strs[0..i-1] → cur[..j] 的顺序拼出候选。为什么：这就是从剪点出发沿环走一圈的顺序；中间部分必须先绕到数组末尾再从头接回来，写成简单的 0..n-1 会把环的相对次序破坏掉。

候选与 answer 比较，更大则替换。为什么：题目只要最终最大值，不需要记录方案，一路打擂台即可。

返回 answer。

以 strs = ["abc", "xyz"] 走一遍。

预处理："abc" 的反转是 "cba"，"cba" > "abc"，替换为 "cba"；"xyz" 的反转是 "zyx"，"zyx" > "xyz"，替换为 "zyx"。此时 strs = ["cba", "zyx"]。

枚举 i = 0（剪 "cba"）。朝向一 cur = "cba"：j = 0 得 "cba" + "zyx" + "" = "cbazyx"，answer 更新为它；j = 1 得 "ba" + "zyx" + "c" = "bazyxc"，比 "cbazyx" 小；j = 2 得 "a" + "zyx" + "cb" = "azyxcb"，更小。朝向二 cur = "abc"：j = 0 得 "abczyx"；j = 1 得 "bczyxa"；j = 2 得 "czyxab"，三者都不敌 "cbazyx"（都以 a、b、c 开头但第二位更小）。

枚举 i = 1（剪 "zyx"）。此时中间部分是 strs[0] = "cba"。朝向一 cur = "zyx"：j = 0 得 "zyx" + "cba" = "zyxcba"，字典序以 z 开头，一举超过之前所有候选，answer 更新；j = 1 得 "yx" + "cba" + "z" = "yxcbaz"；j = 2 得 "x" + "cba" + "zy" = "xcbazy"。朝向二 cur = "xyz"：三个候选分别是 "xyzcba"、"yzcbax"、"zcbaxy"，其中 "zcbaxy" 同样以 z 开头，但第二位 c 小于 "zyxcba" 的 y，仍然落败。

最终返回 "zyxcba"。这个例子恰好展示了两类串的不同待遇："abc" 作为非剪点串时永远以最优形态 "cba" 出现（见 i = 1 的所有候选），而作为剪点串时 "abc" 和 "cba" 两种朝向都被试过了。

代码实现

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 是所有字符串的总长度。凭什么：预处理对每个串做一次反转与比较，合计 $O(m)$；枚举阶段的剪点总数是「每个串的长度之和 × 2 种朝向」即 $O(m)$ 个，而每个剪点都要拼出一个长度为 m 的候选串并与答案做一次长度为 m 的比较，单次 $O(m)$，相乘即 $O(m^2)$。

空间复杂度：$O(m)$。凭什么：每轮用一个 StringBuilder 构造长度为 m 的候选串，用完即弃；answer 也只有 m 长；预处理产生的反转串替换掉原串，不额外增长。峰值同时存在的字符串是常数个，各占 $O(m)$。

关键点总结

面对「每个元素二选一 + 全局最优」的题，先问一句：这些选择之间是否独立。本题里非剪点串的朝向互不影响，可以各自贪心；一旦发现独立性，$2^n$ 立刻塌成 $O(n)$。

独立性的判据是「换掉这一块，其余部分不变」。字典序逐位比较的特性保证了「块更大 ⇒ 整体不更小」，这就是贪心的正确性证明，面试时必须能说出来。

识别出「有且只有一个特殊元素」的结构后，标准套路是枚举谁是特殊的那个，其余用贪心。这是「枚举 + 贪心」组合拳的典型形态，比全枚举低一个指数。

剪点串不能贪心，因为反转同时改变了「哪一半跑到开头」和「字符顺序」，与「整串谁大」不是同一个问题。能主动指出这里贪心失效，比写对代码更能体现理解深度。

环形结构的遍历顺序要写成「从当前位置绕到末尾，再从头接回当前位置之前」，这个两段式拼接是所有环形题的固定零件。

易错点总结

对剪点串也直接用预处理后的单一朝向：strs = ["ab"] → 预处理后变成 "ba"，只枚举它的剪点得到 "ba"、"ab"，恰好答案正确；但换成 strs = ["ba", "z"] 这类输入时，剪点串的另一朝向可能让更大的字符跑到开头，漏掉它会得到偏小的答案。

对非剪点串也逐个枚举两种朝向：n = 20 → 组合数 $2^{20}$，直接超时；而且完全没有必要，贪心已经证明最优。

中间部分按 0 .. n-1 顺序拼接：strs = ["a", "b", "c"]，剪 i = 1 → 拼出的是 "b" + "a" + "b" + "c" 式的错误串，既破坏了环的相对次序，还可能把 strs[i] 重复算进去。

中间部分漏掉「从 0 绕回 i-1」那一段：strs = ["x", "y"]，剪 i = 1 → 结果里完全没有 "x"，长度都不对。

剪点 j 从 1 开始枚举：strs = ["cba", "zyx"] → 丢掉了 j = 0 即「在串的最前面剪」的方案，而 "zyxcba" 正是这样得到的，答案退化成 "yxcbaz"。

剪点 j 枚举到 cur.length()（含）：cur[j..] 为空、cur[..j] 是整串 → 与 j = 0 产生重复候选，虽不影响正确性但白做一轮；若语言对越界下标不宽容则直接抛异常。

用 equals 或长度比较代替字典序比较：Java 里写成 candidate.length() > answer.length() → 所有候选长度都一样，条件恒假，返回空串。

预处理与枚举共用同一份被修改的数组却在枚举中再次修改它：若在内层循环里也把 strs[i] 改成 cur → 后续 i 的枚举读到的中间部分不再是最优形态，答案随枚举顺序漂移。

认为只能在字符串之间的接缝处剪：strs = ["abc"] → 只会得到 "abc" 或 "cba"，而剪在串内部同样合法，会漏掉像 "bca" 这类候选。

相似题目

题目	难度	考察点
179. 最大数	中等	同为拼接求最大字典序，但可以任意重排，靠自定义比较器排序而非枚举
1163. 按字典序排在最后的子串	困难	同样在所有后缀里找最大，但要用双指针把 $O(m^2)$ 优化到线性
556. 下一个更大元素 III	中等	在数位重排中找「刚好比原数大」的那个，考的是字典序的下一个而非最大值
796. 旋转字符串	简单	只需判定两串是否互为旋转，用「拼接自身再查子串」一步到位
316. 去除重复字母	中等	同为字典序最优化，但决策是「删或留」，用单调栈在一趟内贪心完成
402. 移掉 K 位数字	中等	删除固定个数字符求最小，单调栈方向与 316 相反，考的是贪心的方向感
670. 最大交换	中等	只允许一次交换，靠「从右往左记录最大数位」定位唯一的最优交换对
321. 拼接最大数	困难	需要先从两数组各取最优子序列再归并，是枚举与贪心叠加的更复杂形态