LeetCode 471. 编码最短长度的字符串

Categories:

题目描述
思路分析
1. 解法一：区间动态规划（推荐）
相似题目

题目描述

✅ 471. 编码最短长度的字符串

思路分析

解法一：区间动态规划（推荐）

核心思路：

定义 dp[i][j] 为子串 s[i..j] 的最短编码长度

对于任意区间 [i, j]，先初始化为不压缩时的原始长度 j - i + 1

尝试将区间拆分为两段：dp[i][j] = min(dp[i][k] + dp[k+1][j])（对所有 k 取最小）

尝试整体压缩：检查 s[i..j] 是否能表示为某个子串重复 k 次的形式，若能则编码为 k[子串]，长度为 len(子串) + 数字位数 + 2

判断能否重复压缩：利用 KMP 的失配函数，若 (len % (len - fail[len-1])) == 0 则可被整除压缩

复杂度分析：

时间复杂度：O(n^3)，其中 n 为字符串长度，外层区间 O(n^2)，每个区间内枚举分割点和 KMP 各 O(n)

空间复杂度：O(n^2)，dp 数组的空间

class Solution {

  public String encode(String s) {
    int n = s.length();
    // dp[i][j] 表示 s[i..j] 的最短编码
    String[][] dp = new String[n][n];

    // 按区间长度从小到大填表
    for (int len = 1; len <= n; len++) {
      for (int i = 0; i + len - 1 < n; i++) {
        int j = i + len - 1;
        String sub = s.substring(i, j + 1);

        // 初始化为原始字符串（长度 <= 4 时不压缩更短）
        dp[i][j] = sub;

        // 尝试整体压缩（长度 > 4 才有意义）
        if (len > 4) {
          String compressed = getCompressed(sub);
          if (compressed.length() < dp[i][j].length()) {
            dp[i][j] = compressed;
          }
        }

        // 尝试拆分为两段
        for (int k = i; k < j; k++) {
          String candidate = dp[i][k] + dp[k + 1][j];
          if (candidate.length() < dp[i][j].length()) {
            dp[i][j] = candidate;
          }
        }
      }
    }

    return dp[0][n - 1];
  }

  // 检查字符串能否被压缩，若能返回压缩后形式
  private String getCompressed(String s) {
    int n = s.length();

    // KMP 失配函数
    int[] fail = new int[n];
    for (int i = 1; i < n; i++) {
      int j = fail[i - 1];
      while (j > 0 && s.charAt(i) != s.charAt(j)) {
        j = fail[j - 1];
      }
      if (s.charAt(i) == s.charAt(j)) {
        j++;
      }
      fail[i] = j;
    }

    int unitLen = n - fail[n - 1];
    if (n % unitLen == 0) {
      int times = n / unitLen;
      String unit = s.substring(0, unitLen);
      return times + "[" + unit + "]";
    }

    return s;
  }
}

func encode(s string) string {
    n := len(s)
    // dp[i][j] 表示 s[i..j] 的最短编码
    dp := make([][]string, n)
    for i := range dp {
        dp[i] = make([]string, n)
    }

    // 按区间长度从小到大填表
    for length := 1; length <= n; length++ {
        for i := 0; i+length-1 < n; i++ {
            j := i + length - 1
            sub := s[i : j+1]

            // 初始化为原始字符串
            dp[i][j] = sub

            // 尝试整体压缩（长度 > 4 才有意义）
            if length > 4 {
                compressed := getCompressed(sub)
                if len(compressed) < len(dp[i][j]) {
                    dp[i][j] = compressed
                }
            }

            // 尝试拆分为两段
            for k := i; k < j; k++ {
                candidate := dp[i][k] + dp[k+1][j]
                if len(candidate) < len(dp[i][j]) {
                    dp[i][j] = candidate
                }
            }
        }
    }

    return dp[0][n-1]
}

// 检查字符串能否被压缩，若能返回压缩后形式
func getCompressed(s string) string {
    n := len(s)

    // KMP 失配函数
    fail := make([]int, n)
    for i := 1; i < n; i++ {
        j := fail[i-1]
        for j > 0 && s[i] != s[j] {
            j = fail[j-1]
        }
        if s[i] == s[j] {
            j++
        }
        fail[i] = j
    }

    unitLen := n - fail[n-1]
    if n%unitLen == 0 {
        times := n / unitLen
        unit := s[:unitLen]
        return fmt.Sprintf("%d[%s]", times, unit)
    }

    return s
}

相似题目

题目	难度	考察点
394. 字符串解码	中等	栈、递归、字符串
459. 重复的子字符串	简单	KMP、字符串
486. 预测赢家	中等	区间动态规划
516. 最长回文子序列	中等	区间动态规划
647. 回文子串	中等	动态规划、双指针
1312. 让字符串成为回文串的最少插入次数	困难	区间动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/26323550