Find Longest Common Prefix in an Array of Strings

Given an array, arr[] of "n" different strings, the task is to find the longest common prefix among all strings present in the array.

Input: {"cup", "cupboard", "cut", "curse"}, Output: "cu"

Input: {"hit", "duper", "super"}, Output: "-1"

Solutions

The idea is to first calculate the length of shortest string, because the common prefix can not exceed the length of shortest string.

Next, start a loop from "0" to "length of shortest string", and in each iteration check if the i^th character is same in each string.

If i^th character is same in each string, than this character will be part of common prefix.

Else if in any iteration the i^th character is different for any string, return substring of any string from 0 to i.

	package com.cb.arrays;

	/*
	* Time: O(n * length of prefix)
	* Space: O(1)
	* */
	public class A27_LongestCommonPrefix {

	private static String longestCommonPrefix(String arr[], int n) {
	int minLength = Integer.MAX_VALUE;

	// get length of smallest string
	for (int i = 0; i < n; i++)
	if (arr[i].length() < minLength)
	minLength = arr[i].length();

	Character c = null;
	int last = 0;

	// get last common character
	while (last < minLength) {
	for (int j = 0; j < n; j++) {
	if (j == 0)
	c = arr[j].charAt(last);
	else if (arr[j].charAt(last) != c)
	return last == 0 ? "-1" : arr[0].substring(0, last);
	}
	last++;
	}
	return last == 0 ? "- 1" : arr[0].substring(0, last);
	}

	public static void main(String[] args) {
	String arr[] = {"cup", "cupboard", "cut", "curse"};
	System.out.println(longestCommonPrefix(arr, arr.length)); // "2"
	}
	}