Leetcode – 14 – Longest Common Prefix

Longest Common Prefix

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

Description:

In this problem we have to find the common prefix for all the strings in the array.

Solution (two pointers)

The approach that we are talking about is to have two pointers i and j whereas i will iterate for the length of the first string and j will iterate for the length of the array.

We will compare the first character in the first string with the characters of all other strings characters

We will have to use StringBuilder to append the prefix character found so far at the end of each of the loop.

1

Code:

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        StringBuilder strB = new StringBuilder();
        if(strs != null && strs.length != 0){
            String str1 = strs[0];
            for(int i = 0; i < str1.length(); i++){
                char ch = str1.charAt(i);
                for(String str : strs) {
                    if(str.length() < i + 1 || str.charAt(i) != ch)
                        return strB.toString();
                }
                strB.append(ch);
            }
        } 
        return strB.toString();
    }
}

Time Complexity: O(n2)

  • Go through the length of each string(m) and then number of strings in the array(n) – O(mn) -> O(n2)

Space Complexity: O(1)

  • We will store each of the characters  – O(1)

Available Test Cases: 117

  • Check for empty String
  • Check for case sensitive
  • Check for null case
  • Check with different lengths
  • Check with all same
  • Check with special characters

Github:

Leetcode_14_Longest_Common_Prefix

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: