# 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

### Crawler Log Folder - minimum number of operations needed to go back to the main folder after the change folder operations.

Problem The Leetcode file system keeps a log each time some user performs a…

### Remove nth Node from Last - Leet Code Solution

Problem Statement Given a linked list, remove the n-th node from the end of list…

### Leetcode - Maximum Non Negative Product in a Matrix

Problem Statement You are given a rows x cols matrix grid. Initially, you are…

### Leetcode - Split a String Into the Max Number of Unique Substrings

Problem Statement Given a string s, return the maximum number of unique…

### Counting Inversions Coding Problem

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

### Rotate Image - Leet Code Solution

Problem Statement You are given an n x n 2D matrix representing an image, rotate…

## Latest Posts

### Python SMTP Email Code - How to Send HTML Email from Python Code with Authentication at SMTP Server

Introduction This post has the complete code to send email through smtp server…

### Python SMTP Email Code - Sender Address Rejected - Not Owned By User

Introduction In a normal email sending code from python, I’m getting following…

### Nodejs with MongoDB - Number of Opened Connections Keep on Increasing with Mongoose Library

Introduction In one of my app, I was using to talk to . I have used some event…

### Django Python - How to Build Docker Image and Run Web-service on Apache with Python 3.9

Introduction So you have a Django project, and want to run it using docker image…

### Python - How to Maintain Quality Build Process Using Pylint and Unittest Coverage With Minimum Threshold Values

Introduction It is very important to introduce few process so that your code and…

### Example Jenkin Groovy Pipeline Script for Building Python Projects with Git Events and Push to Artifactory

Introduction In this post, we will see a sample Jenkin Pipeline Groovy script…