LeetCode 555. 分割连接字符串

Categories:

题目描述
思路分析
1. 解法一：贪心 + 枚举（推荐）
相似题目

题目描述

✅ 555. 分割连接字符串

思路分析

解法一：贪心 + 枚举（推荐）

核心思路：

对于每个字符串，可以选择正向或反向拼接。为了让某个位置成为分割点后得到最大字典序结果，需要枚举每个字符串的每个位置作为分割点。

预处理：对每个字符串，先将其与反转串比较，选字典序更大的方向作为”基准方向”——这样在非分割字符串上贪心取最大。

枚举分割点：固定某个字符串 i 的某个字符 j 为分割点，结果 = strs[i][j..end] + 其余字符串（贪心选最大方向）+ strs[i][0..j]。

对所有候选结果取字典序最大值。

复杂度分析：

时间复杂度：O(n × L²)，其中 n 为字符串数量，L 为字符串平均长度，枚举分割点需 O(n × L)，每次拼接耗时 O(n × L)

空间复杂度：O(n × L)，存储拼接结果

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 ans = "";

    // 枚举每个字符串的每个字符作为分割起点
    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++) {
          // 拼接：cur[j..] + 其他字符串（已贪心选最大） + cur[..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(ans) > 0) {
            ans = candidate;
          }
        }
      }
    }

    return ans;
  }
}

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
        }
    }

    ans := ""

    // 枚举每个字符串的每个字符作为分割起点
    for i := 0; i < n; i++ {
        rev := reverse(strs[i])

        for _, cur := range []string{strs[i], rev} {
            for j := 0; j < len(cur); j++ {
                // 拼接：cur[j..] + 其他字符串（已贪心选最大） + 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 > ans {
                    ans = candidate
                }
            }
        }
    }

    return ans
}

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)
}

相似题目

题目	难度	考察点
344. 反转字符串	简单	字符串、双指针
179. 最大数	中等	贪心、排序
316. 去除重复字母	中等	贪心、栈
767. 重构字符串	中等	贪心、字符串
1163. 按字典序排在最后的子串	困难	双指针、字符串
678. 有效的括号字符串	中等	贪心、字符串

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/74299718