Fast and simple Java code 231ms


  • 28
    P
    public class Solution {
        public String longestCommonPrefix(List<String> strs) {
            if(strs.size()==0) return "";
            StringBuilder lcp=new StringBuilder();
            for(int i=0;i<strs.get(0).length();i++){
                char c=strs.get(0).charAt(i);
                for(String s:strs){
                    if(s.length()<i+1||c!=s.charAt(i)) return lcp.toString();
                }
                lcp.append(c);
            }
            return lcp.toString();
        }
    }

  • 0
    J

    nice solution.1 vote for you..


  • 4
    C

    You can actually add another line of code to check if the size of strs==1, then just return strs[0] and save all of the iteration later.


  • 10

    Rather than building the string for common prefix, you can just record the longest prefix's length, then return the substring from first character till that length, which can save a bit time perhaps.

    The code is as below written in javascript:

    var longestCommonPrefix = function(strs) {
        if (strs.length === 0) return "";
        if (strs.length === 1) return strs[0];
    
        for (var i = 0; i < strs[0].length; i++) {
            for (var j = 1; j < strs.length; j++) {
                if (strs[j].length <= i || strs[j][i] !== strs[0][i]) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    };
    
    console.log(longestCommonPrefix(['this is a test', 'this is also a test']));
    console.log(longestCommonPrefix(['this is a test', 'this is a test as well']));

  • 5

    What about finding the shortest length of the strings in the array first? I think it's better than checking the length of every string in the double-layer loop body.

    My solution is as follows.

    public class Solution {
        public String longestCommonPrefix(String[] strs) {
    		if (strs == null || strs.length == 0)
    			return "";
    		int numOfArr = strs.length;
    		int lenOfStr = strs[0].length();
    		for (int i = 1; i < numOfArr; i++) {
    			if (strs[i].length() < lenOfStr)
    				lenOfStr = strs[i].length();
    		}
    		
    		for (int i = 0; i < lenOfStr; i++) {
    			char c = strs[0].charAt(i);
    			for (int j = 1; j < numOfArr; j++) {
    				if (strs[j].charAt(i) != c)
    					return strs[0].substring(0, i);
    			}
    		}
    		
    		return strs[0].substring(0, lenOfStr);
        }
    }

  • 1

    The answer is not correct anymore since leetcode has updated the input param, plz find the updated version below:

    public class Solution {
        public String longestCommonPrefix(String[] strs) {
            if(strs == null || strs.length == 0) return "";
            StringBuilder lcp = new StringBuilder();
            for(int i=0;i<strs[0].length();i++){
                char c=strs[0].charAt(i);
                for(String s:strs){
                    if(s.length()<i+1||c!=s.charAt(i)) return lcp.toString();
                }
                lcp.append(c);
            }
            return lcp.toString();
        }
    }
    

  • 1

    I am really wondering that are we solving the same problem??
    Please do not change the data type of the input value. That's totally wrong even though your code can handle the new data type


  • 0
    N

    @pengfeifc said in Fast and simple Java code 231ms:

    public class Solution {
        public String longestCommonPrefix(List<String> strs) {
            if(strs.size()==0) return "";
            StringBuilder lcp=new StringBuilder();
            for(int i=0;i<strs.get(0).length();i++){
                char c=strs.get(0).charAt(i);
                for(String s:strs){
                    if(s.length()<i+1||c!=s.charAt(i)) return lcp.toString();
                }
                lcp.append(c);
            }
            return lcp.toString();
        }
    }
    

    is the strs List sorted ?


  • 0
    Y

    @Harrywithcode You can see the answer posted one year ago, the problem you mentioned mainly due to the website updates...


Log in to reply
 

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