# Longest Common Prefix

Given the array of strings A,
you need to find the longest string S which is the prefix of ALL the strings in the array.

Longest common prefix for a pair of strings S1 and S2 is the longest string S which is the prefix of both S1
and S2.

For Example, longest common prefix of "abcdefgh" and "abcefgh" is "abc".

Input Format

```The only argument given is an array of strings A.
```
Output Format

```Return longest common prefix of all strings in A.
```
For Example

```Input 1:
A = ["abcdefgh", "aefghijk", "abcefgh"]
Output 1:
"a"
Explanation 1:
Longest common prefix of all the strings is "a".

Input 2:
A = ["abab", "ab", "abcd"];
Output 2:
"ab"
Explanation 2:
Longest common prefix of all the strings is "ab".```
###### Method

Find the shortest string, and then check character one by one.

Solution:

Time: O(n * length of min string)
Space: O(length of min string)

```public class Solution {
public String longestCommonPrefix(ArrayList<String> A) {
int len = Integer.MAX_VALUE;
for (String s : A) {
if (s.length() < len) {
len = s.length();
}
}
StringBuilder prefix = new StringBuilder();
for (int i = 0; i < len; i ++) {
char c = A.get(0).charAt(i);
for (int j = 1; j < A.size(); j ++) {
char n = A.get(j).charAt(i);
if (c != n) {
return prefix.toString();
}
}
prefix.append(c);
}
return prefix.toString();
}
}```

```class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
StringBuilder sb = new StringBuilder();
int j = 0;
String first = strs;
while (j < first.length()) {
char c = first.charAt(j);
boolean exit = false;
for (int i = 1; i < strs.length; i ++) {
if (j >= strs[i].length() || strs[i].charAt(j) != c) {
exit = true;
break;
}
}
if (exit) break;
sb.append(c);
j ++;
}
return sb.toString();
}
}```