How to find longest common prefix in an array of strings.
Given an array of strings, write a method to find the longest common prefix string. If no common prefix is found, return an empty string ” “.
For example:
Example 1:
Input: [“cat”,”cable”,”camera”]
Output: “ca”
The longest common prefix is ca.
Example 2:
Input: [“rat”,”dog”,”elephant”]
Output: “”
No common prefix is found.
In this tutorial, I am going to discuss the algorithm and their java implementation to find the longest common prefix amongst an array of strings.
Longest Common Prefix
Find First Non-repeating character in a string
Find Longest Common Prefix in an Array of Strings – Java Code
To understand this, let’s suppose there are two strings cat and cable. What’s the longest common prefix in both of them? It’s ca.
Let’s take the third word camera into the consideration. After that, still the longest common prefix is ca.
|
1 2 3 4 5 |
LCP(str1, str2, str3) = LCP (LCP (str1, str2), str3) LCP(cat, cable, camera) = LCP ( LCP (cat, cable), camera) = LCP (ca, camera) = "ca" |
To solve this, let’s assume the string present at 0th index is the longest common prefix so far. After that take the next string and compare with the LCP so far.
We have to compare the each character of the current string with longest common prefix string found so far. After the complete iteration, the final result will be our longest common prefix of all the strings.
Longest common prefix video tutorial
|
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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
/* Find the longest common prefix java code */ public class LongestCommonPrefix { public static String findLongestPrefix(String[] strs) { //If string array is null or empty if(strs == null || strs.length == 0) { return ""; } //Assign first word of an array string String lcp = strs[0]; //Traverse an array from 1 to n-1 for(int i = 1; i < strs.length; i++) { String currentWord = strs[i]; int j = 0; /* While common character is found, increment the value of j */ while(j < currentWord.length() && j < lcp.length() && currentWord.charAt(j) == lcp.charAt(j)) { j++; } //If no common character is found if(j == 0) { return ""; } //Assign common substring lcp = currentWord.substring(0,j); } return lcp; } public static void main(String[] args) { String[] strgs = {"cat","cable","camera"}; String result = findLongestPrefix(strgs); System.out.println(result); } } |
Longest Common Prefix LeetCode Solution
|
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 |
//LeetCode Solution class Solution { public String longestCommonPrefix(String[] strs) { if(strs == null || strs.length == 0) { return ""; } String lcp = strs[0]; for(int i = 1; i < strs.length; i++) { String currentWord = strs[i]; int j = 0; while(j < currentWord.length() && j < lcp.length() && currentWord.charAt(j) == lcp.charAt(j)) { j++; } if(j == 0) { return ""; } lcp = currentWord.substring(0,j); } return lcp; } } |
Check whether two strings are anagram of each other
