Practice › Strings
Longest Common Prefix
Easy · Strings · Asked at Amazon, Google, Microsoft, TCS, Infosys
Find the longest common prefix of all the given words. Print -1 if there is no common prefix.
Input
First line: n. Second line: n words separated by spaces.
Output
The longest common prefix, or -1.
Constraints
- 1 ≤ n ≤ 200
- 1 ≤ word length ≤ 200
Example 1
Input
3 flower flow flight
Output
fl
Example 2
Input
3 dog racecar car
Output
-1
Hints
- The answer can be no longer than the first word.
- Shorten a candidate prefix (start with the first word) until every other word starts with it.
Approach
Take the first word as the prefix. For each other word, compare character by character and cut the prefix at the first mismatch, or at the shorter length. If the prefix ever becomes empty there is no common prefix: print -1.
Complexity: O(total characters) time · O(1) extra space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<string> w(n);
for (auto &x : w) cin >> x;
string prefix = w[0];
for (int i = 1; i < n; i++) {
size_t k = 0;
while (k < prefix.size() && k < w[i].size() && prefix[k] == w[i][k]) k++;
prefix = prefix.substr(0, k);
}
cout << (prefix.empty() ? "-1" : prefix) << "\n";
return 0;
}Python solution
import os
n = int(input())
words = input().split()
prefix = os.path.commonprefix(words[:n])
print(prefix if prefix else -1)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String prefix = sc.next();
for (int i = 1; i < n; i++) {
String w = sc.next();
int k = 0;
while (k < prefix.length() && k < w.length() && prefix.charAt(k) == w.charAt(k)) k++;
prefix = prefix.substring(0, k);
}
System.out.println(prefix.isEmpty() ? "-1" : prefix);
}
}