Posts Longest Common Prefix in an Array (geeksforgeeks - SDE Sheet)
Post
Cancel

Longest Common Prefix in an Array (geeksforgeeks - SDE Sheet)

PROBLEM DESCRIPTION

Given an array of N strings, find the longest common prefix among all strings present in the array. Return “-1” if there is no common prefix.

geeksforgeeks

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
34
35
36
37
38
39
40
class Solution{

    String longestCommonPrefix(String arr[], int n){

        // Initialize the longest common prefix with the first string in the array
        String lcp = arr[0];

        // Iterate through the array of strings starting from the second string
        for(int i=1; i<n; i++){

            // Update the longest common prefix by finding the common prefix between the current prefix and the next string
            lcp = commonPrefix(lcp, arr[i]);

        }

        // If no common prefix is found, return "-1", otherwise return the longest common prefix
        return lcp.equals("") ? "-1" : lcp.toString();

    }

    // Method to find the common prefix between two strings
    String commonPrefix(String s1, String s2){

        // Create a StringBuffer to store the common prefix
        StringBuffer sb = new StringBuffer();

        int i = 0;

        // Iterate through the strings as long as there are characters left in both strings and the characters are equal
        while(i < s1.length() && i < s2.length() && s1.charAt(i) == s2.charAt(i)){
            // Append the current character to the common prefix, and move to next char
            sb.append(String.valueOf(s1.charAt(i)));
            i++;
        }

        return sb.toString();

    }

}
This post is licensed under CC BY 4.0 by the author.