My 35ms O(n^2) DP with O(n) space


  • 1
    Z
    class Solution {
    public:
      int minCut(string s) {
        // the state is 1-based
        vector<int> palindrome_numbers(s.size() + 1);
        fill(palindrome_numbers.begin(), palindrome_numbers.end(), -1);
        palindrome_numbers[0] = 0;
    
        init(s);
    
        for (int i = 1; i <= s.size(); i++) {
          for (int j = 0; j < i; j++ ) {
            if (palindrome_numbers[j] != -1 && is_palindrome(j + 1, i)) {
              if (palindrome_numbers[i] == -1)
                palindrome_numbers[i] = palindrome_numbers[j] + 1;
              else
                palindrome_numbers[i] = min(palindrome_numbers[i], palindrome_numbers[j] + 1);
            }
          }
        }
        return palindrome_numbers[s.size()]-1;
      }
    private:
    
      vector<int> span;
    
      void init(const string &s) {
        span.resize(s.size() * 2);
        for (int i = 0; i < s.size(); i++) {
          int a = i , b = i;
          span[a + b] = calc_span(s, a, b);
          if (i != s.size() - 1) {
            int a = i, b = i + 1;
            span[a + b] = calc_span(s, a, b);
          }
        }
      }
    
      int calc_span(const string &s, int a, int b) {
        while (a >= 0 && b < s.size() && s[a] == s[b]) a--, b++;
        return b - 1 - (a + 1);
      }
    
      // [a, b]
      bool is_palindrome(int a, int b) {
        //change 1-based to 0-based;
        a--, b--;
        return span[a + b] >= b - a;
      }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.