Java DP + Memorization


  • 2
    W
       public int strangePrinter(String s) {
            if (s == null || s.length() == 0) {
                return 0;
            }
    
            int size = s.length();
            int[][] dp = new int[size][size];
    
            for (int i = 0; i < size; i++) {
                dp[i][i] = 1;
            }
    
            return helper(dp, 0, size - 1, s);
    
        }
    
        private int helper(int[][] dp, int x, int y, String s) {
            int size = s.length();
    
            if (x < 0 || x >= size || y < 0 || y >= size) {
                return 0;
            } else if (x > y) {
                return 0;
            } else if (dp[x][y] != 0) {
                return dp[x][y];
            } else {
    
                if (s.charAt(y) != s.charAt(y - 1)) {
                    dp[x][y] = helper(dp, x, y - 1, s) + 1;
                } else {
                    dp[x][y] = helper(dp, x, y-1, s);
                }
    
                for (int i = 0; i < y; i++) {
                    if (s.charAt(i) == s.charAt(y)) {
                        dp[x][y] = Math.min(dp[x][y], helper(dp, x, i, s) + helper(dp, i + 1, y - 1, s));
                    }
                }
    
                return dp[x][y];
            }
        }
    

Log in to reply
 

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