# Longest Common Prefix - Leet Code Solution

September 13, 2019

## Problem Statement

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 "".

Example 1:
Input: ["flower","flow","flight"]
Output: "fl"

Example 2:
Input: ["dog","racecar","car"]
Output: ""

Note: All given inputs are in lowercase letters a-z.

## Solution-1

Lets look at a simple solution, where we will look in entire strings for the match.

1. We have to search in all strings
2. Lets take length of first string. Result can not be greater than the length of smallest string. We are just taking first string.
3. Now, iterate to this length.
• Take first character of first string
• Iterate over all strings
• And, match that character from first string in all other strings
• If matched, append it to our result.
• Else, just break down.
public String longestCommonPrefix(String[] strs) {
int strsLen = strs.length;
if (strsLen == 0) {
return "";
}
int l = strs[0].length();

StringBuffer sb = new StringBuffer();
for (int i=0; i<l; i++) {
char ch = strs[0].charAt(i);
boolean matched = true;
for (int j=1; j<strsLen; j++) {
if (i >= strs[j].length() || ch != strs[j].charAt(i)) {
matched = false;
break;
}
}
if (!matched) {
break;
}
sb.append(ch);
}

return sb.toString();
}

## Solution-2

We can use divide and conquer, and then merge the result. Since, common of two strings will be eligible to match from other strings.

• Divide the string array, untill it remains single
• Then, merge such single strings. Means, just find longest common prefix in these two strings.
• In subsequent recursion, we will be comparing two common prefixes with each other.
• Recursively do this, and combine results in the end.
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) return "";
return helper(strs, 0, strs.length-1);
}

private String findRes(String l, String r) {
int len = Math.min(l.length(), r.length());
int i=0;
for (; i<len; i++) {
if (l.charAt(i) != r.charAt(i)) {
break;
}
}

return l.substring(0, i);
}
private String helper(String[] strs, int l, int r) {
if (l == r) return strs[l];

int m = (l+r)/2;
String left = helper(strs, l, m);
String right = helper(strs, m+1, r);

return findRes(left, right);
}

## Similar Posts

### Counting Sort Algorithm

Counting sort runs on relatively smaller set of input. Counting sort calculates…

### Longest Palindrome Substring - Leet Code Solution

Problem Statement Given a string s, find the longest palindromic substring in s…

### Counting Inversions Coding Problem

** Inversion There is an array(a) and two indexes i and j. Inversion is the…

### Integer to Roman conversion - Leet Code Solution

Problem Statement Roman numerals are represented by seven different symbols: I…

### Quick Sort Algorithm

This algorithm is very useful for large input. And, is quite efficient one. It…

### Container with Most Water - Leet Code Solution

Problem Statement Given n non-negative integers a1, a2, …, an , where each…

## Latest Posts

### Jenkins Pipeline with Jenkinsfile - How To Schedule Job on Cron and Not on Code Commit

Introduction In this post we will see following: How to schedule a job on cron…

### How to Git Clone Another Repository from Jenkin Pipeline in Jenkinsfile

Introduction There are some cases, where I need another git repository while…

### How to Fetch Multiple Credentials and Expose them in Environment using Jenkinsfile pipeline

Introduction In this post, we will see how to fetch multiple credentials and…

### Jenkins Pipeline - How to run Automation on Different Environment (Dev/Stage/Prod), with Credentials

Introduction I have an automation script, that I want to run on different…

### Jenkinsfile - How to Create UI Form Text fields, Drop-down and Run for Different Conditions

Introduction I had to write a CICD system for one of our project. I had to…

### Java Log4j Logger - Programmatically Initialize JSON logger with customized keys in json logs

Introduction Java log4j has many ways to initialize and append the desired…