CareerCup

There could be multiple aproaches for this,

(1) Tries seems a simple solution, but we have to go through each and every string and add it to a trie. This is memory extensive, unless you keep dropping the unmatched chracters in tries. If you do so It is same as option (2)

(2) Consider he t1st String as the common prefix, now consider second and find till what point it matches, consider the string till that point as new common prefix...keep on rectifying the common prefix. This is good approach
Time Complexity O(n * avg(string size)). The worst case would kill the system. Lets say all the n-1 string are same, but the last string has only one character in common. This would only stop after completing all the work.

(3) Read every character one by one from all the strings and break something doesnot match. o(n * (commonPrefixSize+1)).

It would stop when one string has uncommon character. I think this is the better solution. The only point to mention here would be, if the string array is really huge and you cannot load all the string in memory in one go. Then this would take more time. But overall this is better solution.

public String longestCommonPrefix(String[] strings)
	{
		if (strings.length == 0)
		{
			return "";
		}

		char prevChar;
		if (strings[0].length() > 0)
		{
			prevChar = strings[0].charAt(0);
		}
		else
		{
			return "";
		}

		int i;
		loop:
			for (i = 0; ; ++i)
			{
				if (strings[0].length() > i)
				{
					prevChar = strings[0].charAt(i);
				}

				for (int j = 0; j < strings.length; ++j)
				{
					//				System.out.println("j is: " + j + " and i is: " + i );
					if (i < strings[j].length() && strings[j].charAt(i) != prevChar || i >= strings[j].length())
					{
						break loop;
					}
				}
			}

		return strings[0].substring(0, i);

}

function longest_common_prefix($strings){
	$str1_words = str_word_count($strings[0], 1);
	for($i=0; $i<count($str1_words); $i++){
		for($j=1; $j<count($strings); $j++){
			$str_words = str_word_count($strings[$j], 1);
			if(count($str_words) === $i || $str_words[$i] !== $str1_words[$i]){
				return implode(" ", array_slice($str1_words, 0, $i));
			}
		}
	}
	
	return FALSE;
}

$strings = array("i love all dogs", "i love cats");
echo longest_common_prefix($strings);

Use a trie, put all N strings in a trie and keep a count of the length of the longest prefix seen.

Simple recursive solution:

private static void findCommonPrefixRec(String[] phrases, StringBuilder sb, int pos) {
        String sample = phrases[0];
        boolean match = Arrays.stream(phrases).allMatch(s -> s.length() > pos && s.charAt(pos) == sample.charAt(pos));

        if (match) {
            sb.append(phrases[0].charAt(pos));
            findCommonPrefixRec(phrases, sb, pos + 1);
        }
    }

public static string Longest(IEnumerable<string> strings){
		try{
			var first = strings.First();
			int size = 1;
			string result = string.Empty;
			string predicate = first.Substring(0,size);
			while(strings.All(x => x.StartsWith(predicate))){
				size++;
				result = predicate;
				predicate = first.Substring(0,size);
			}
			return result;
		} catch(Exception e){
			return string.Empty;
		}
	}

string longestCommonPrefix(vector<string> strings) {
  if (strings.size()==0) return "";
  string prefix = strings[0];
  for (size_t i=1; i<strings.size(); ++i) {
    char *prefixIter = &prefix[0];
    char *strValIter = &((strings[i])[0]);
    int count = 0;
    while (*prefixIter == *strValIter) {
      ++count;
      ++prefixIter;
      ++strValIter;
    }
    prefix = strings[i].substr(0,count);
  }
  return prefix;
}

Sort the array.. Scan through the array and Find the longest prefix by comparing with only one previous item in the array.. e.g substring method can be used in Java .. It would be very simple code with N+NlogN complexity..

Sort the list [Collections.sort(List) in java], complexity: NlogN


In sorted list:
- Go through each item from 0 till item-2
- compare with next item
- store the longest common prefix in a variable during the scan (easy to do)

After the scan, we have longest common prefix: N

So, in total it is: NlogN + N.

This one does not use sorting but finds the min length string. then compares each string upto that length with temp char array.

public static String getPrefix(List<String> phrases){
		
		if(phrases == null || phrases.size() == 0)
			return "";
		
		if(phrases.size() == 1)
			return phrases.get(0);
		
		int minCounter = Integer.MAX_VALUE;
		int length = Integer.MAX_VALUE, i=0, counter=0;
		
		for(String str : phrases){
			if(length > str.length()){
				length = str.length();
				counter=i;
			}
			i++;
		}
		
		char [] chars =  phrases.get(counter).toCharArray();
		
		for(i=0;i<phrases.size();i++){
			String str = phrases.get(i);
			int len = str.length();
			int j;
			for(j=0; j<len && j<chars.length && chars[j]==str.charAt(j); j++);
			if(j < minCounter)
				minCounter = j;
		}
		
		return phrases.get(0).substring(0, minCounter);	
	}

What about this guys?

private static String getLongestCommonPrefix(String[] items){
      int min = 0;
    
      for(int i=0;i<items.length;i++){
          if(min==0 || min>items[i].length()){
              min = items[i].length();
          }
      }
    
    
      while(min>0){
        if(areEqualToAll(min)){
          return items[1].substring(0,min);
        }else{
          min--;
        }
      }
    
    return "Cannot find";
  }
  
  private static boolean areEqualToAll(int min){
    for(int i=0;i<items.length;i++){
          String first = items[i].substring(0,min);
          
          for(int j=0;j<items.length;j++){
            
            String second = items[j].substring(0,min);
            if(!first.equals(second)){
              return false;
            }
          
          }
      }
    return true;
  }

#include<iostream>
#include<string>
#include<list>
using namespace std;

class Data
{
public:
Data()
{
minSizeData = -1;
largestCommonPrefix.clear();
}

void addData(const string &s)
{
if (minSizeData < 0)
minSizeData = s.length();
else if (minSizeData > s.length())
{
minSizeData = s.length();
}

l.push_back(s);
}

string& maxCommonPrefix()
{
int currentPosition = 0;
char ch;
bool running = true;

if ((l.size() == 0) )
{
cout << endl << "No Elements in the list so returning the empty string..." << endl;
return largestCommonPrefix;
}

largestCommonPrefix.clear();

if ((l.size() == 1))
{
largestCommonPrefix.assign(*(l.begin()));
return largestCommonPrefix;
}

list<string>::const_iterator c_list_itr;
string::const_iterator c_str_itr;

for (int i = 0;(i < minSizeData)&&(running==true);i++)
{
c_list_itr = l.begin();
c_str_itr = c_list_itr->begin();
ch = *(c_str_itr + currentPosition);
c_list_itr++;
for (c_list_itr;c_list_itr != l.end();c_list_itr++)
{
c_str_itr = c_list_itr->begin();
if (ch != *( c_str_itr + currentPosition) )
{
running = false;
break;
}
}

if (running)
{
largestCommonPrefix.push_back(ch);
currentPosition++;
}
}

return largestCommonPrefix;
}

private:
list<string> l;
string largestCommonPrefix;
int minSizeData;
};

int main()
{
Data d;


d.addData(string("I love dogs"));
d.addData(string("I love cats"));
d.addData(string("I love you"));

cout << endl << d.maxCommonPrefix() << endl;

return 0;
}

package test;

import java.util.*;

public class ComPrefix {

	public static void main(String[] args) {
		String[] str={"i love all dogs", "i love cats"};
		System.out.println(findComPrefix(str));
	}
	
	
	public static String findComPrefix(String[] str){
		List<String> list =new ArrayList<>();
		for(String s:str[0].split(" ")){
			list.add(s);
		}
		int len = list.size();
		for(int i=1; i<str.length; i++){
			int j=0;
			for(String s: str[i].split(" ")){
				if(j>=len){
					break;
				}
				if(!list.get(j).equals(s)){
					len = j;
					break;
				}
				j++;
			}
		}
		StringBuilder sb= new StringBuilder();
		for(int i=0; i<len;i++){
			sb.append(list.get(i)).append(" ");
		}
		return sb.length()>0 ? sb.deleteCharAt(sb.length()-1).toString() : null;
	}

}

package test;

import java.util.*;

public class ComPrefix {

	public static void main(String[] args) {
		String[] str={"i love all dogs", "i love cats"};
		System.out.println(findComPrefix(str));
	}
	
	
	public static String findComPrefix(String[] str){
		List<String> list =new ArrayList<>();
		for(String s:str[0].split(" ")){
			list.add(s);
		}
		int len = list.size();
		for(int i=1; i<str.length; i++){
			int j=0;
			for(String s: str[i].split(" ")){
				if(j>=len){
					break;
				}
				if(!list.get(j).equals(s)){
					len = j;
					break;
				}
				j++;
			}
		}
		StringBuilder sb= new StringBuilder();
		for(int i=0; i<len;i++){
			sb.append(list.get(i)).append(" ");
		}
		return sb.length()>0 ? sb.deleteCharAt(sb.length()-1).toString() : null;
	}

}

Use longest common prefix algorithm along with suffix array. en.wikipedia.org/wiki/LCP_array

Longest common prefix means both need to start at the same point.
Am I wrong?

private static String commonPrefix(String s1, String s2) {
		StringBuilder sb = new StringBuilder();
		int min = Math.min(s1.length(), s2.length());
		
		for (int i = 0; i < min; i++) {
			if (s1.charAt(i) != s2.charAt(i))
				break;
				
			sb.append(s1.charAt(i));
		}
		
		return sb.toString();
	}

Sort the list.. [Collections.sort(List) in java] (complexity: NlogN)
In sorted list:
go through each item
compare with previous (or next) item
update the substring if String.find(substring) is more than the stored value of max substringIndex.


return the max substring in after the scan. (complexity: N)

So it is N + NlogN. not bad with simple and short code. :)