CareerCup

public String longPrefix(String str){
	String arr[] = str.split(“ “);
	int len = arr[0].length;
	int p;
	for(int i =1; i < arr.length;i++){
		p=0;
		while(p < len && p < arr[i].length 
                            && arr[0].charAt(p) == arr[i].charAt(p))
			p++;
		len = p;
	}
	return arr[0].subString(0,len);
}

public static String longPrefix(String str)
{
String[] words = str.split(" ");
for(int j = 0; ; j++)
for(int i = 1; i < words.length; i++)
if ( words[0].charAt(j) != words[i].charAt(j))
return words[0].substring(0, j);
}

public class HelloWorld{
    public static String findLongestPrefix(String[] words){
   
   String prefix=words[0]; 
   
   for(int i=1;i<words.length;i++){
           if(prefix.length()>words[i].length()) prefix=prefix.substring(0,words[i].length());
           for(int j=0;j<prefix.length();j++){
               if(prefix.charAt(j)!=words[i].charAt(j)){
                 prefix=prefix.substring(0,j);
                 break;
               } 
                }
            }
            if(prefix.equals("")) return "";
         return prefix;   
        }        

     public static void main(String []args){
        
        System.out.println("Hello World new");
        String[] words={
            "akaleeee","akale","akalear","akaleaer","akalemoss"
        };
         System.out.println(findLongestPrefix(words));
     }
}

/**
	 * K - prefix length
	 * N - strings count 
	 * time: O(K*N)
	 * space: O(K)
	 */
	String findLongestPrefix(String[] arr) {

		if (arr == null) {
			throw new IllegalArgumentException();
		}

		if (arr.length == 0) {
			return "";
		}

		StringBuilder prefix = new StringBuilder();

		String firstStr = arr[0];
		int firstStrLength = firstStr.length();
		
		MAIN: 
		for (int charIndex = 0; charIndex < firstStrLength; charIndex++) {

			char ch = firstStr.charAt(charIndex);

			for (int i = 1; i < arr.length; i++) {
				
				String otherStr = arr[i];
				
				if ( otherStr.length() <= charIndex || otherStr.charAt(charIndex) != ch ) {
					break MAIN;
				}
			}

			prefix.append(ch);
		}

		return prefix.toString();
	}

USE A TRIE

# To change this template, choose Tools | Templates
# and open the template in the editor.
# code is implemented in the ruby
class Test

def findSequence(number)
words = number.split(" ")
@@index = 0
for i in 0...words[0].length
for j in 1...words.size
# puts j;
if words[j][i] == words[0][i]
next
else
@@index = i
puts words[0][0,@@index]
return
end
end
end
end


end

@test = Test.new
@test.findSequence("ankifbvh sdcds sd sdcds")

This is brute force and not the best solution. Will post more later ...

public StringBuilder bruteForceLCP (String str) {
		StringBuilder sub = new StringBuilder();
	
		String[] words = str.split(" ");
		
		for (String word : words) {
			for (int i = 0; i< word.length(); i++) {
				
				if (sub.length() >= word.length()) {
					continue;
				}
				
				if (sub.length() > 0 && sub.length() > i) {
					i = sub.length();
				}
				
			    String c = word.substring(0, i+1);
			    boolean isSubstring = true;
				
			    for (String wrd : words) {
					if (!wrd.startsWith(c)) {
						isSubstring = false;							
					}				
				}
				if (isSubstring) {
					System.out.println("Prefix found : " + c);
					sub.replace(0, (sub.length()), c);					
				}
			}
		}
	System.out.println("*****Longest common sub prefix : " + sub);
	return sub;
		
	}

Use trie to insert all words and then check for the longest commong length

Initially assume first word is the longest common prefix. check if each character in the rest of the words is exactly same, if not return the substring of first word.

public String longestCommonPrefix(String[] strs) {
        if(strs == null || strs.length == 0)
            return "";
        
        String lcp = strs[0];
        for(int i =0; i < lcp.length(); i++)
        {
            for(int j =1; j <strs.length; j++)
            {
                if(i >= strs[j].length() || lcp.charAt(i) != strs[j].charAt(i)) 
                    return lcp.substring(0,i);
            }
        }
        return lcp;
    }

maybe sort it by length first, and start with the shortest and match with next one, find the common part and use it to match with next one and so on...

/// Find the longest sequence of prefix shared by all the words in a string.
/// "abcdef abcdxxx abcdabcdef abcyy" => "abc"
public void FindLongestSequenceOfPrefix(string sentence)
{
string[] array = sentence.Split(' ');
array = array.OrderBy(s => s).ToArray();

Dictionary<string, int> hash = new Dictionary<string, int>();
foreach (var s in array)
{
var str1 = s;
var index = Compare(array, s, 0, 0, ref str1);
if (!hash.ContainsKey(str1))
{
hash.Add(str1, index - 1);
}
}
}

int Compare(string[] array, string s, int index, int prevCount, ref string str1)
{
if (index >= s.Length)
return prevCount;

int count1 = 0;
foreach (var str in array)
{
if (str[index] == s[index])
{
count1++;
}
}

if (count1 < prevCount)
{
str1 = s.Substring(0, index);
return prevCount;
}
else
{
prevCount = count1;
return Compare(array, s, index + 1, prevCount, ref str1);
}
}

string longestCommonPrefix(vector<string> &strs) {
string result;
if(strs.empty()) //这是为空的情况
return result;
if(strs.size()==1) //这是大小为1的情况
return *(strs.begin());

//下面讨论的是至少大小为2的情况
int minLength,i=0;
vector<string>::const_iterator iter=strs.begin();
minLength=(*iter).size();
for(;iter!=strs.end();++iter)
if((*iter).size()<minLength)
minLength=(*iter).size();
while(i<minLength)
{
for(iter=strs.begin();iter!=strs.end()-1;++iter)
{
if(*((*iter).begin()+i)!=*((*(iter+1)).begin()+i))
break;
}
if(iter==strs.end()-1)
{
result+=*((*iter).begin()+i);
i++;
}
else
break;
}
return result;
}

string longestCommonPrefix(vector<string> &strs) {
string result;
if(strs.empty()) //这是为空的情况
return result;
if(strs.size()==1) //这是大小为1的情况
return *(strs.begin());

//下面讨论的是至少大小为2的情况
int minLength,i=0;
vector<string>::const_iterator iter=strs.begin();
minLength=(*iter).size();
for(;iter!=strs.end();++iter)
if((*iter).size()<minLength)
minLength=(*iter).size();
while(i<minLength)
{
for(iter=strs.begin();iter!=strs.end()-1;++iter)
{
if(*((*iter).begin()+i)!=*((*(iter+1)).begin()+i))
break;
}
if(iter==strs.end()-1)
{
result+=*((*iter).begin()+i);
i++;
}
else
break;
}
return result;
}

str1="abcdef abcdxxx abcdabcdef abcyy"
def getstr(str1,str2):
str=""
for i in range(0,len(str1)):
if i<len(str2):
if str1[i]==str2[i]:
str+=str1[i]
else:
break
return str
def func(str1):
str1=str1.split()
str=getstr(str1[0],str1[1])
for i in range(2,len(str1)):
str=getstr(str1[i],str)
return str
print func(str1)

public static string LongestPrefix(string str)
        {
            string[] arr = str.Split(' ');
            string prefix = string.Empty;
            string firstWord = arr[0];
            for (int j = 0; j < firstWord.Length; j++ )
            {
                char c = firstWord.ElementAt(j);
                bool common = true;
                for(int i = 1; i < arr.Length; i++)
                {
                    if(arr[i].ElementAt(j) != c)
                    {
                        common = false;
                    }
                }
                if (common)
                    prefix += c;
                else
                    return prefix;
            }

                return prefix;
        }

I am able to think of two solutions :

First one :

* Assume the first word is the common prefix.
* Let there be L pointing to second word and R pointing to last word.
* Let PC hold common prefix. So, its initial value will be the first word.
1. Next, find common prefix between PC and second word AND PC and last word.
2. Take the smallest prefix from above and set this in PC.
3. Increment L and decrment R.
4. Repeat 1 to 3 until L > R

Second one :

* Start scanning for words in sentence, and for each word found, add them to a suffix tree (compressed trie)
* From suffix tree, will get the common prefix.

Test cases :

* Empty sentence
* Sentence with single word or 2 words
* Sentence with significant number of words
* Sentence with no common prefix among words

Approach 1:

Let the words in the sentence be defined as w0, w1, ... , wn. Let prefix (LP) be defined as w0.
For each word wi in w1 ... wn {
	LP = common_prefix(LP, wi)
	if (LP.isEmpty())
		return LP
}
return LP
==================================================
Now it all depends how we calculate common_prefix(). We can use trie to generate a structure once when LP is initialized and use the same data structure to find out the prefix. or we can use two pointers to get the common prefix strings each time in the function.

Approach 2:
This approach is slight modification of the approach 1.
Assuming that the words are delimited by space character, we will not find any words separately and then iterate over words. In fact, we will iterate over sentence and perform common_prefix() operation on the word within the string.

public static String findCommonSuffix(final String sentence) {
        if (sentence  == null) throw new NullPointerException("String is null");

        if (sentence.length() == 0) return "";

        // Initialize LP first
        StringBuilder LP = new StringBuilder();
        for (int i = 0; sentence.charAt(i) != ' '; i++) {
            LP.append(sentence.charAt(i));
        }

        // Move the forward pointer to the next non-space character
        int next = LP.length();
        while (next < sentence.length()) {
            int s = next;
            while (s < sentence.length() && sentence.charAt(s) == ' ') s++;
            if (s == sentence.length()) return LP.toString();

            StringBuilder temp = new StringBuilder();
            for (int j = 0; j < LP.length() && s < sentence.length() && sentence.charAt(s) == LP.charAt(j); j++, s++) {
                temp.append(LP.charAt(j));
            }

            LP = null;
            LP = temp;
            if (LP.length() == 0) return LP.toString();
            if (s == sentence.length()) return LP.toString();
            while (s < sentence.length() && sentence.charAt(s) != ' ') s++;
            next = s;
        }

        return LP.toString();
    }

In Java

public static String longestPrefix(String str){

        String[] arr = str.split(" ");
        char[] firstStr = arr[0].toCharArray();

        for (int i = 0; i < firstStr.length; i++) {
            for (int j = 1; j < arr.length; j++) {
                if (arr[j].length() <= i || firstStr[i] != arr[j].charAt(i)) {
                    return arr[0].substring(0, i);
                }
            }
        }
        return arr[0];
    }

public static String longPrefix(String str)
    {
        String[] words = str.split(" ");
        for(int j = 0; ; j++)
        {
            for(int i = 1; i < words.length; i++)
            {
                if ( words[0].charAt(j) != words[i].charAt(j))
                    return words[0].substring(0, j);
            }
        }
    }

Split into words, then use a recursive approach on the list of words, taking off one letter at a time. First in Python (concise), then in "C" using pointers into the existing word for efficiency.

Python:

import sys


def find_longest_prefix(words):
    if any(len(word) == 0 for word in words):
        return ''
    if all([word[0] == words[0][0] for word in words]):
        return words[0][0] + find_longest_prefix([word[1:] for word in words])
    return ''

if __name__ == '__main__':
    print find_longest_prefix([word for word in sys.argv[1].split(' ') if word])

Same apparcoh in "C" for efficiency, allocating only an array of pointers to identify words, and space for the prefix to be stored.

#include <string>
#include <stdio.h>
#include <stdlib.h>

void find_prefix(char **words, char *prefix)
{
    int i;
    char *word = words[0];
    if (!word[0])
    {
        return;
    }
    char prech = word[0];
    for (i=0;;i++)
    {
        if (!words[i])
        {
            break;
        }
        if (words[i][0] != prech)
        {
            return;
        }
        words[i] = &words[i][1];
    }
    *prefix = prech;
    find_prefix(words, &prefix[1]);
}

int main(int argc, char * argv[])
{
    /* Split argv[1] into words, then find longest prefix */
    /* First, identify spaces and NULL terminate them, keeeping */
    /* an array of pointers to each word's start */
    int i=0;
    char *start = argv[1];
    char *prefix = (char *) malloc(strlen(argv[1]));
    /* worst case, need length of string / 2 + 1 pointers */
    char **words = (char **)malloc(sizeof(char *) * (strlen(argv[1]) / 2 + 1));
    memset(words, 0, sizeof(words[0]) * strlen(argv[1]) / 2 + 1);
    words[0] = start;
    while (*start++)
    {
        if (*start == ' ')
        {
            while (*start == ' ')
            {
                *start++ = '\0';
            }
            words[++i] = start;
        }
    }
    prefix[0] = '\0';
    find_prefix(words, prefix);
    printf("%s\n", prefix);
    free(words);
    free(prefix);
}

std::string longest_prefix(const std::string& sentence) {
  
  // split sentence into a vector of words...
  std::istringstream iss(sentence);
  std::vector<std::string> words(std::istream_iterator<std::string>{iss}, {});
  
  unsigned n;
  for (n = 0; n < words[0].size(); ++n) {
    const char c = words[0][n];
    const auto f = [=](const std::string& word) { return word[n] == c; };
    // break if c is not the n-th letter of all words...
    if (!std::all_of(words.begin(), words.end(), f))
      break;
  }
  return sentence.substr(0, n);
}

public static void main(String[] args) {
System.out.println(new StringPrefix().printPrefix("abcdef abcdxxx abcdabcdef abcyy"));
}

public String printPrefix(String str){
String tempHead;
String[] strList = str.split(" ");
for (int i = 0; i< strList[0].length(); i++)
{
tempHead = strList[0].substring(0, i);
for (String s : strList)
{
int index = s.indexOf(tempHead);
if (index < 0)
{
return tempHead.substring(0, tempHead.length() - 1);
}
}
}
return "";
}

public static void main(String[] args) {
		System.out.println(new StringPrefix().printPrefix("abcdef abcdxxx abcdabcdef abcyy"));
	}
	
	public String printPrefix(String str){
		String tempHead;
		String[] strList = str.split(" ");
		for (int i = 0; i< strList[0].length(); i++)
		{
			tempHead = strList[0].substring(0, i);
			for (String s : strList)
			{
				int index = s.indexOf(tempHead);
				if (index < 0)
				{
					return tempHead.substring(0, tempHead.length() - 1);
				}
			}
		}
		return "";
	}

public static void main(String[] args) {
		System.out.println(new StringPrefix().printPrefix("abcdef abcdxxx abcdabcdef abcyy"));
	}
	
	public String printPrefix(String str){
		String tempHead;
		String[] strList = str.split(" ");
		for (int i = 0; i< strList[0].length(); i++)
		{
			tempHead = strList[0].substring(0, i);
			for (String s : strList)
			{
				int index = s.indexOf(tempHead);
				if (index < 0)
				{
					return tempHead.substring(0, tempHead.length() - 1);
				}
			}
		}
		return "";
	}

pre = ""
for  i in range(len(str)):
    if(str[i] != ' '):    
        pre = pre + str[i];
    else:
        break; 
       
n = i+1 
l = i-1;
x = 0;

while (n < len(str)):
    print n, x;
    if x <= l  and str[n] == pre[x] :
        x = x+1;
        n = n+1;
        continue;
    else:
        l = x-1;
        x = 0;
        while(n < len(str) and str[n] != ' ' ):
            print n , x;
            n = n+1;
    n=n+1;
     
print pre[:l+1] ,  l;

One pass solution...

public class PrefixMatching {

	public static void main (String []args) {
		String s1 = "ABCDEF";
		String s2 = "ABCDEFGH";
		String s3 = "ABCDSAD";
		String result = "";
		
		int i=0, j=0, k=0;
		
		while (i < s1.length() && j < s2.length() && k < s3.length()) {
			
			if (s1.charAt(i) == s2.charAt(j) && s2.charAt(j) == s3.charAt(k)) {
				result += s1.charAt(i);
				i++;
				j++;
				k++;
			}
			else {
				break;
			}
		}
		
		System.out.println("Result: "+result);
	}
}

What about using Suffix Tree?
and finding the branch node which contains all inputs?

What about using Suffix Tree?
and finding the branch node which contains all inputs?

public class LongestSequence {
  public static String longestSequence(String s) {
    String[] tokens = s.split(" ");
    String prefix = "", next = "";

    String reference = tokens[0];

    for (int i = 1; i <= reference.length(); i++) {
      prefix = reference.substring(0, i);
      next = reference.substring(0, i+1);
      for (String token : tokens) {
        if (i >= token.length() || !token.startsWith(next)) {
          return prefix;
        }
      }
    }

    return prefix;
  }


  public static void main(String[] args) {
    System.out.println(longestSequence(args[0]));
  }
}

Just need 3 ints and one pass over the string (plus iterating over the common prefix m times)

static int GetPrefixLength(string s)
        {
            int length = -1;
            int prefixIndex = 0;

            for(int i = 0; i < s.Length && length != 0; i++)
            {
                if (prefixIndex < length)
                {
                    if (s[i] == s[prefixIndex])
                        prefixIndex++;
                    else
                        length = prefixIndex;
                }

                if (Char.IsWhiteSpace(s[i]))
                {
                    prefixIndex = 0;
                    if (length < 0)
                        length = i;
                }
            }

            return prefixIndex;
        }

var input="abcdef abcdxxx abcdabcdef abcyy";
var words=input.split(" ");
words.sort(function(a,b){return a.length-b.length});

var result="";
for (var i=0;i<words[0].length;i++){
for (var j=1;j<words.length;j++){
if (words[0][i]!=words[j][i]){
break;
}
}
if (j==words.length) {
result+=words[0][i];
}
}

console.log(result);

Using regular expressions (O(n)) and exponential growth (log(m) where m<n is the length of the first word and <=n)
brings the total runtime to O(n*log(m))
Can be further optimized by picking the shortest word for m and scanning the words string minus that word.

import re
def max_prefix(words):
    if not words:
        return None
    words = words.lstrip()
    num = len(re.findall(r"\w+",words,re.I))
    lim=len(words)
    i=1
    step=1
    last_good=0
    while i<lim:
        if len(re.findall(r"\b"+words[:i],words))==num:
            last_good=i
            i+=step
            step*=2
        else:
            lim=i
            step=1
            i=i/2+step
    
    if last_good>0:
        return words[:last_good]
    else:
        return None

package careerCupGoogle;

public class longestPrefixString 
{
	String[] testCases = {"abcdef abcdxxx abcyy abcdabcdef"};
	
	public static void main(String[] args) 
	{
		longestPrefixString obj = new longestPrefixString();
		for(int i=0;i<obj.testCases.length;i++)
		{	
			System.out.println("\nTest Case: "+i);
			System.out.println("\tInput : "+obj.testCases[i]);
			
			System.out.println("\n\tResult : "+obj.calculateFunction(obj.testCases[i]));
		}

	}

	private String calculateFunction(String string) 
	{	
		int prefix_length = 0;
		String[] words = string.split(" ");
		int total_words = words.length;
		//find the smallest word
		String min_word = words[0];
		int min_word_len = words[0].length();
		for(int i=1;i<words.length;i++)
		{
			if(words[i].length()<min_word_len)
			{
				min_word = words[i];
				min_word_len = words[i].length();
			}
		}
		System.out.println(min_word);
		
		for(int i=min_word_len-1;i>=0;i++)
		{	
			
			int words_count_compliance = 0;
			for(int j=0;j<words.length;j++)
			{
				if(min_word.charAt(i)==words[j].charAt(i))
					words_count_compliance++;
			}
			if(words_count_compliance!=total_words)
			{
				prefix_length = i-1;
				break;
			}
		}
		
		return words[0].substring(0, prefix_length);
	}
	
	

}

One approach would be:-

Consider smallest string (1st string) as prefix. Search if its substring of other strings.
If no, then consider first half of 1st string and do same till we can get final string

Find lexicographical smallest string, and biggest string, just find common prefix of them.

One pass solution.

std::string getLongestPrefix(const std::string& str) {
  // Prefix of first word is whole first word. 
  int prefix = 0;
  while (prefix < str.size() && str[prefix] != ' ') {
    prefix++;
  }

  for (int pos = prefix+1; pos < str.size(); pos++) {
    int word_prefix = 0;
    while (pos < str.size() &&
           word_prefix < prefix &&
           str[pos] == str[word_prefix]) {
      word_prefix++; pos++;
    }
    prefix = word_prefix;
    while (pos < str.size() && str[pos] != ' ')
      pos++;
  }
  
  return str.substr(0, prefix);
}

It is not needed, but here is a Trie-based working solution in C++.

#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
using namespace std;

struct Node{
    int prefixOf;
    Node *children[26];
};

Node *createNode(){
    Node *node = new Node;
    node->prefixOf = 0;
    for (int i = 0; i < 26; i++)
        node->children[i] = NULL;

    return node;
}

void insert(Node *node, string s){
    for (int i = 0; i < (int)s.size(); i++){
        node->prefixOf++;
        char c = s[i];
        int idx = c - 'a';
        if (node->children[idx] == NULL)
            node->children[idx] = createNode();
        node = node->children[idx];
    }
}

string longestPrefix = "";

void traverse(Node *node, string s, int N){
    if (node->prefixOf == N && (int)s.size() > (int)longestPrefix.size()){
        longestPrefix = s;
    }

    for (int i = 0; i < 26; i++){
        if (node->children[i] != NULL)
            traverse(node->children[i], s + (char)(i + 'a'), N);
    }
}

int main(){
    vector<string> words;
    int N;
    cin >> N;

    Node *root = createNode();

    string s;

    for (int i = 0; i < N; i++){
        cin >> s;
        insert(root, s);
    }

    traverse(root, "", N);
    cout << longestPrefix << endl;
    return 0;
}

Since it's pretty easy, I wanted to have some fun with it:

def (string):
  a = map(lambda x: len(set(x)), zip(*map(lambda x: list(x), string.split(" "))))
  while a[total] == 1:
    total += 1
  print string[:total] # assumes the string starts with a word, not space

#include<iostream>
#define SIZE 4

using namespace std;

int main(){
    string str[SIZE] = {"abcdf", "abcdefx", "abcdefcdef", "abcdy"};
    string str1 = str[0];
    int minCount = 0;
    int index = 0;
    int prevIndex = 0;
    
    for(int i=0; i< SIZE-1;i++){
        string str1 = str[i];
        string str2 = str[i+1];
        index = 0;
        for(int j=0, k=0 ; j<str1.length() && k<str2.length(); j++,k++){
            if(str1[j] != str2[k])
                break;
            //cout<<j<<" ";
            if(j>index)
                index = j;
        }
        if(i==0)
            prevIndex = index;
        
        if(prevIndex < index)
            index = prevIndex;
        
    }
    str1 = str[0];
    for(int i=0; i<=index; i++)
        cout<<str1[i];
    cout<<endl;
    
    return 0;
}

Direct Trie Usecase figure out the common prefix before branching

def main(args: String[]) {
   }