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 "".
Link of problem: https://leetcode.com/problems/longest-common-prefix/
Algorithm
-
Sort the array of strings in alphabetical order.
-
Compare the characters in the first and last strings in the array. Since the array is sorted, common characters among the first and last element will be common among all the elements of the array.
2.1. If they are same, then append the character to the
result.2.2. Else, stop the comparison –
resultcontains the longest common prefix among the strings in the array.
The below diagram showing how the algorithm works
            |
Java Code
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
import java.util.*; public class Test { public static String longestCommonPrefix(String[] strs) { if (strs.length > 0) { Arrays.sort(strs); char[] firstStrChArray = strs[0].toCharArray(); String lastStr = strs[strs.length - 1]; String result = ""; for (int i = 0; i < firstStrChArray.length; i++) { String finalStr = result + firstStrChArray[i]; if (lastStr.startsWith(finalStr)) { result += String.valueOf(firstStrChArray[i]); } else { break; } } return result; } return ""; } public static void main(String[] args) { System.out.println(longestCommonPrefix(new String[]{"flower","flow","flight"})); } } |
Source: https://www.educative.io/edpresso/how-to-find-the-longest-common-prefix-in-an-array-of-strings
Leave a Reply