Skip to content

471. Encode String with Shortest Length 👍

Approach 1: Top-down

  • Time: $O(n^4)$
  • Space: $O(n^3)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
 public:
  string encode(string s) {
    const int n = s.length();
    // dp[i][j] := shortest encoded string of s[i..j]
    dp.resize(n, vector<string>(n));
    return encode(s, 0, n - 1);
  }

 private:
  vector<vector<string>> dp;

  string encode(const string& s, int i, int j) {
    if (!dp[i][j].empty())
      return dp[i][j];

    const string& curr = s.substr(i, j - i + 1);
    dp[i][j] = curr;

    if (dp[i][j].length() < 5)
      return dp[i][j];

    // try all possible partitions
    for (int k = i; k < j; ++k) {
      const string& l = encode(s, i, k);
      const string& r = encode(s, k + 1, j);
      if (l.length() + r.length() < dp[i][j].length())
        dp[i][j] = l + r;
    }

    // try to compress the string
    // e.g. s = aabaabaab -> 3[aab]
    for (int k = i; k <= j; ++k) {
      const string& pattern = s.substr(i, k - i + 1);
      if (curr.length() % pattern.length() == 0 &&
          regex_replace(curr, regex(pattern), "").empty()) {
        const string& candidate = to_string(curr.length() / pattern.length()) +
                                  '[' + encode(s, i, k) + ']';
        if (candidate.length() < dp[i][j].length())
          dp[i][j] = candidate;
      }
    }

    return dp[i][j];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
  public String encode(String s) {
    final int n = s.length();
    // dp[i][j] := shortest encoded String of s[i..j]
    dp = new String[n][n];
    return encode(s, 0, n - 1);
  }

  private String[][] dp;

  private String encode(final String s, int i, int j) {
    if (dp[i][j] != null)
      return dp[i][j];

    final String curr = s.substring(i, j + 1);
    dp[i][j] = curr;

    if (dp[i][j].length() < 5)
      return dp[i][j];

    // try all possible partitions
    for (int k = i; k < j; ++k) {
      final String l = encode(s, i, k);
      final String r = encode(s, k + 1, j);
      if (l.length() + r.length() < dp[i][j].length())
        dp[i][j] = l + r;
    }

    // try to compress theString
    // e.g. s = aabaabaab -> 3[aab]
    for (int k = i; k <= j; ++k) {
      final String pattern = s.substring(i, k + 1);
      if (curr.length() % pattern.length() == 0 && curr.replaceAll(pattern, "").isEmpty()) {
        final String candidate =
            String.valueOf(curr.length() / pattern.length()) + "[" + encode(s, i, k) + "]";
        if (candidate.length() < dp[i][j].length())
          dp[i][j] = candidate;
      }
    }

    return dp[i][j];
  }
}

Approach 2: Bottom-up

  • Time: $O(n^4)$
  • Space: $O(n^3)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
 public:
  string encode(string s) {
    const int n = s.length();
    // dp[i][j] := shortest encoded string of s[i..j]
    vector<vector<string>> dp(n, vector<string>(n));

    for (int d = 0; d < n; ++d) {
      for (int i = 0; i + d < n; ++i) {
        const int j = i + d;
        const string& curr = s.substr(i, j - i + 1);
        dp[i][j] = curr;

        if (dp[i][j].length() < 5)
          continue;

        // try all possible partitions
        for (int k = i; k < j; ++k)
          if (dp[i][k].length() + dp[k + 1][j].length() < dp[i][j].length())
            dp[i][j] = dp[i][k] + dp[k + 1][j];

        // try to compress theString
        // e.g. s = aabaabaab -> 3[aab]
        for (int k = i; k <= j; ++k) {
          const string& pattern = s.substr(i, k - i + 1);
          if (curr.length() % pattern.length() == 0 &&
              regex_replace(curr, regex(pattern), "").empty()) {
            const string& candidate =
                to_string(curr.length() / pattern.length()) + '[' + dp[i][k] +
                ']';
            if (candidate.length() < dp[i][j].length())
              dp[i][j] = candidate;
          }
        }
      }
    }

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
  public String encode(String s) {
    final int n = s.length();
    // dp[i][j] := shortest encoded String of s[i..j]
    String[][] dp = new String[n][n];

    for (int d = 0; d < n; ++d) {
      for (int i = 0; i + d < n; ++i) {
        final int j = i + d;
        final String curr = s.substring(i, j + 1);
        dp[i][j] = curr;

        if (dp[i][j].length() < 5)
          continue;

        // try all possible partitions
        for (int k = i; k < j; ++k)
          if (dp[i][k].length() + dp[k + 1][j].length() < dp[i][j].length())
            dp[i][j] = dp[i][k] + dp[k + 1][j];

        // try to compress theString
        // e.g. s = aabaabaab -> 3[aab]
        for (int k = i; k <= j; ++k) {
          final String pattern = s.substring(i, k + 1);
          if (curr.length() % pattern.length() == 0 && curr.replaceAll(pattern, "").isEmpty()) {
            final String candidate =
                String.valueOf(curr.length() / pattern.length()) + "[" + dp[i][k] + "]";
            if (candidate.length() < dp[i][j].length())
              dp[i][j] = candidate;
          }
        }
      }
    }

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