Java DP solution


  • 0
    A

    Using dynamic programming

    public class Solution {
        public String longestCommonPrefix(String[] strs) {
            int n = strs.length;
            if(n == 0){return ""; }if(n == 1){return strs[0];}
            String[] dp = new String[n];
            dp[0] = strs[0]; 
            for(int i = 1; i < n; i++){
                boolean pass = false;
                String prev = dp[i-1];
                String current = strs[i]; 
                int minLength = Math.min(prev.length(), current.length());
                for(int j = 0; j < minLength; j++){
                    if(prev.charAt(j) != current.charAt(j)){
                        if(j == 0){
                            return "";
                        } else{
                            dp[i] = prev.substring(0, j);
                            pass = true;
                            break;
                        }
                    }
                }
                if(pass){
                    continue;
                } else{
                   dp[i] = dp[i-1].substring(0, minLength);
                }
            }
            return dp[n-1];
        }
    }
    

Log in to reply
 

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