LeetCode Solutions

			

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

			

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

			

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