Longest Common Prefix

Solution

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

 

Examples

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

 

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

 

Explanation

class Solution {
    public String longestCommonPrefix(String[] strs) {
        Arrays.sort(strs);
        String first = strs[0];
        String last = strs[strs.length - 1];
        int idx = 0;
        while(idx < first.length() && idx < last.length()){
            if(first.charAt(idx) == last.charAt(idx)) idx++;
            else break;
        }
        return first.substring(0, idx);
    }
}

 

1. Sort the given array, strs

If the array is sorted alphabetically, then you can assume that the first value of the array and the last value of the array will have the most different prefixes of all comparisons that could be made between strings in the array. If this is true, you only have to compare these two strings.

 

2. Loop through the first and last value in the given array

Using the while loop, we check if a character of first and a character of last are the same for each index. If it is, idx is increment. Otherwise, the loop is finished by a break statement.

 

3. Return a result

After the loop is ended, return a substring of the first element.