The title

LeetCode problem 14, the longest common prefix

Write a function to find the longest public prefix in an array of strings. Returns the empty string "" if no public prefix exists. Example 1: Input: STRS = ["flower","flow","flight"] Output: "FL" Example 2: Input: STRS = ["dog","racecar","car"] Output: "" Description: The input does not have a public prefix. Tip: 0 <= strs.length <= 200 0 <= STRS [I]. Length <= 200 STRS [I] consists of lowercase letters onlyCopy the code

Time to solve the problem.

class Solution {
    public String longestCommonPrefix(String[] strs) {



    }
}
Copy the code

The method input parameters are given above to complete the answer.

Subject analysis

  1. If the string array length is 0, the public prefix is empty
  2. Create a new StringBuilder to store common prefixes
  3. Use the first character to compare to the next, and then concatenate
  4. If different, exit the loop and return the prefix

Answers to analysis

This article only analysis I do the idea, only for reference, to understand a solution to the idea, other kinds of ideas to do the problem please access the Internet.

Answer successful: Execution time :3 ms, beat 20.87% of Java users memory consumption :38.5 MB, beat 7.64% of Java users

This problem I used a more violent crack, direct double cycle comparison, and then return the result.

This answer is accompanied by recommended answers, you can directly read the view!

Class Solution {public String longestCommonPrefix(String[] STRS) {// Create StringBuilder to store the public prefix StringBuilder sb = new StringBuilder(); If (strs.length > 0) {// First = STRS [0]; char[] chars = first.toCharArray(); For (int I = 0; i < chars.length; i++) { boolean isSame = true; for (int j = 0; j < strs.length; j++) { if (strs[j].length() > i) { if (String.valueOf(chars[i]).equals(String.valueOf(strs[j].charAt(i)))) { isSame = true; }else { isSame=false; break; } } else { isSame = false; break; } } if (! isSame) { break; } if (isSame) {// if (isSame) { } } return sb.toString(); } else { return ""; }}}Copy the code

Recommend the answer

When the string array length is 0, the public prefix is empty, directly return the value of the longest public prefix ANS as the first string, initialize the following strings, compare them with ANS, and find the public prefix in pairs. The final result is the longest public prefix. If ans is empty during the search, there is no direct return time complexity for the public prefix: O (s) O (s), Class Solution {public String longestCommonPrefix(String[] STRS) {if(strs.length == 0) return ""; String ans = strs[0]; for(int i =1; i<strs.length; i++) { int j=0; for(; j<ans.length() && j < strs[i].length(); j++) { if(ans.charAt(j) ! = strs[i].charAt(j)) break; } ans = ans.substring(0, j); if(ans.equals("")) return ans; } return ans; }}Copy the code