Java solution, DP


  • 19
    class Solution {
        public int strangePrinter(String s) {
            int n = s.length();
            if (n == 0) return 0;
            
            int[][] dp = new int[101][101];
            for (int i = 0; i < n; i++) dp[i][i] = 1;
            
            for (int i = 1; i < n; i++) {
                for (int j = 0; j < n - i; j++) {
                    dp[j][j + i] = i + 1;
                    for (int k = j + 1; k <= j + i; k++) {
                        int temp = dp[j][k - 1] + dp[k][j + i];
                        if (s.charAt(k - 1) == s.charAt(j + i)) temp--;
                        dp[j][j + i] = Math.min(dp[j][j + i], temp);
                    }
                }
            }
            return dp[0][n - 1];
        }
    }
    

  • 1
    Z

    @shawngao said in Java solution, DP:

    for (int i = 0; i < n; i++) dp[i][i] = 1;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n - i; j++) {
                dp[j][j + i] = i + 1;
                for (int k = j + 1; k <= j + i; k++) {
                    int temp = dp[j][k - 1] + dp[k][j + i];
                    if (s.charAt(k - 1) == s.charAt(j + i)) temp--;
                    dp[j][j + i] = Math.min(dp[j][j + i], temp);
                }
            }
        }
        return dp[0][n - 1];
    

    Can you explain why the 2D array is trying to calculate?
    I am trying to solve with recursion but I can start from front or back but can't find a way to start from middle.


  • 2
    K

    I removed some redundant dp[j][k - 1] + dp[k][j + i] ops as we only need to check-and-merge left-hand side with every occurrence of the same character on the right (correct me if I'm wrong).

    #define forn(i,n) for(int i = 0; i < (n); i++)
    class Solution {
    public:
        int strangePrinter(string s) {
            int dp[101][101], N = s.size();
            if(N <= 1) return N;
            forn(i, N) dp[i][i] = 1;
            for(int i = N-2; i >= 0; i--){
                for(int j = i+1; j < N; j++){
                    dp[i][j] = dp[i+1][j] + 1;
                    char c = s[i];
                    for(int k = i; k < j; k++){
                        if(s[k+1] == c) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]-1);
                    }
                }
            }
            return dp[0][N-1];
        }
    };
    

  • 0
    B

    @zaw_moe so as some posters wrote, it's quite similar to the remove boxes question (#546), the 2D arrays holds the minimum number of printings needed between letters [i...j].


  • 0
    Z

    @shawngao This might be the best answer. However, can you explain what 'k' stands for or, in other words: how can you prove the optimal sub_structure?


  • 0
    Z

    @baselRus Thank you. I am now running the code to understand the if checking in the K loop.


  • 9
    Z

    @zhangsikai123
    what the algorithms doing is

    1. it sets basic print to 1 per character
      2.it sets [i][i] to 1, which means any substring start from i to i (basically a single char).
    2. it add 1 to the printing needs as soon as there is extra char. after [i]loop and [j]loop.
    3. then it checks substring between [i] and [j] which is [k]
      then it minus the printing needs as soon as it found a same char. (it uses the data from last run so basically it is checking one char per turn)
    4. [i] is decreasing. [j] is increasing. which means it is checking from the middle with k running between i and j.
    5. it uses the Math.min to check wether [i][j] value (which can be lower if there is alot of character common from start to end) and take the lower value.
    6. return the substring [0] [n-1] , i.e. the whole string value back.

    When i saw the problem, my instincts told me it is recursive pattern. This is clever execution of recursion into iteration and use keys avoid repetitive calculations.

    Thanks everybody for sharing.


  • 0
    This post is deleted!

  • 0
    Z

    @zaw_moe Tks!


  • 4

    renamed the variables which may be easier to understand:

    int strangePrinter(string s) {
        // # steps to print s[i, j]
        std::vector<std::vector<int>> buffer(s.length(), std::vector<int>(s.length(), 0));
        for (int len = 1; len <= s.length(); ++len) {
            for (int left = 0; left < s.length() - len + 1; ++left) {
                int right = left + len - 1;
                buffer[left][right] = len; // print one char at a time
                // try print [left, k] && [k+1, right]
                for (int k = left; k < right; ++k) {
                    int steps = buffer[left][k] + buffer[k+1][right];
                    if (s[left] == s[k+1] || s[k] == s[right]) {
                        --steps;
                    }
                    buffer[left][right] = std::min(buffer[left][right], steps);
                }
            }
        }
        return buffer.empty() ? 0 : buffer[0][s.length() - 1];
    }
    

Log in to reply
 

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