TLE in Dynamic Programming solution Java Code


  • -1
    B

    Hi,
    I am getting TLE for this DP Solution can anyone suggest some Improvement.

    public class Solution {
                public int minCut(String str) {
                    		int n = str.length();
    
        /*C[i][j] = Minimum number of cuts needed for palindrome partitioning
                         of substring str[i..j]
               P[i][j] = true if substring str[i..j] is palindrome, else false
               C[i][j] is 0 if P[i][j] is true */
    
            		int C[][] = new int[n][n];
            		boolean P[][] = new boolean[n][n];
    
             // Every substring of length 1 is a palindrome
    
            		for (int i = 0; i < n; i++) {
            			C[i][i] = 0;
            			P[i][i] = true;
            		}
    
             /* L is substring length. Build the solution in bottom up manner by
           considering all substrings of length starting from 2 to n.*/
    
            		for (int L = 2; L <= n; L++) {
    
            // If L is 2, then  just need to compare two characters. Else
                // need to check two corner characters and value of P[i+1][j-1]
    
            			for (int i = 0; i < n - L + 1; i++) {
            				int j = i + L - 1;
            				if (L == 2) {
            					P[i][j] = (str.charAt(i) == str.charAt(j));
            
            				} else {
            					P[i][j] = (str.charAt(i) == str.charAt(j))
            							&& P[i + 1][j - 1];
            				}
            				if (P[i][j] == true) {
            					C[i][j] = 0;
            				} else {
            					C[i][j] = 10000;
    
              // Make a cut at every possible localtion starting from i to j,
                    // and get the minimum cost cut.
    
            					for (int k = i; k <= j - 1; k++)
            						C[i][j] = Math.min(C[i][j], C[i][k] + C[k + 1][j] + 1);
            				}
            			}
            		}
            		return C[0][n-1];
                }
            }

Log in to reply
 

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