14_Longest_common_prefix

// https://leetcode.com/problems/longest-common-prefix/

// My approach (Not working)

class Solution {
    public String longestCommonPrefix(String[] strs) {
        int ascii[] = new int[256];
        if(strs.length==0)return "";
        int min = 9999,count = 0;
        for(int i = 0;i<strs.length;i++)
        {
            String s = strs[i];
            count = 0;
            for(int j=0;j<s.length();j++)
            {
                if(i==0)
                {
                    ascii[s.charAt(j)]++;
                    count++;
                }
                else
                {
                    if(ascii[s.charAt(j)]>0)
                    {
                     count++;   
                    }
                }
                
            }
            System.out.println(count);
            if(min>count)
                min = count;
        }
        String ans = "";
        for(int i=0;i<min;i++)
            ans+=strs[0].charAt(i);
        return ans;
    }
}

// My solution (Working)

class Solution{
    public String longestCommonPrefix(String[] strs){
        if(strs.length==0)return "";
        if(strs.length<=1)return strs[0];
        int min = 9999;
        for(int i=0;i<strs.length;i++)
        {
            int len = strs[i].length();
            if(min>len)
                min = len;
        }
        int k = 0;
        String ans = "";
        int f = 0;
        while(k<min)
        {
            char ch = strs[0].charAt(k);
            f = 0;
            for(int i=1;i<strs.length;i++)
            {
                if(ch==strs[i].charAt(k))
                    f=1;
                else
                {
                    f=0;
                    break;
                }
            }
            if(f==1)
                ans+=ch;
            else
                break;
            k++;
        }
        return ans;
    }
}

// Solution 1

 public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) return "";
    String prefix = strs[0];
    for (int i = 1; i < strs.length; i++)
        while (strs[i].indexOf(prefix) != 0) {
            prefix = prefix.substring(0, prefix.length() - 1);
            if (prefix.isEmpty()) return "";
        }        
    return prefix;
}

// Solution 2

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

// Solution 3

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";    
        return longestCommonPrefix(strs, 0 , strs.length - 1);
}

private String longestCommonPrefix(String[] strs, int l, int r) {
    if (l == r) {
        return strs[l];
    }
    else {
        int mid = (l + r)/2;
        String lcpLeft =   longestCommonPrefix(strs, l , mid);
        String lcpRight =  longestCommonPrefix(strs, mid + 1,r);
        return commonPrefix(lcpLeft, lcpRight);
   }
}

String commonPrefix(String left,String right) {
    int min = Math.min(left.length(), right.length());       
    for (int i = 0; i < min; i++) {
        if ( left.charAt(i) != right.charAt(i) )
            return left.substring(0, i);
    }
    return left.substring(0, min);
}

// Solution 4

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0)
        return "";
    int minLen = Integer.MAX_VALUE;
    for (String str : strs)
        minLen = Math.min(minLen, str.length());
    int low = 1;
    int high = minLen;
    while (low <= high) {
        int middle = (low + high) / 2;
        if (isCommonPrefix(strs, middle))
            low = middle + 1;
        else
            high = middle - 1;
    }
    return strs[0].substring(0, (low + high) / 2);
}

private boolean isCommonPrefix(String[] strs, int len){
    String str1 = strs[0].substring(0,len);
    for (int i = 1; i < strs.length; i++)
        if (!strs[i].startsWith(str1))
            return false;
    return true;
}

// Solution 5

public String longestCommonPrefix(String q, String[] strs) {
    if (strs == null || strs.length == 0)
         return "";  
    if (strs.length == 1)
         return strs[0];
    Trie trie = new Trie();      
    for (int i = 1; i < strs.length ; i++) {
        trie.insert(strs[i]);
    }
    return trie.searchLongestPrefix(q);
}

class TrieNode {

    // R links to node children
    private TrieNode[] links;

    private final int R = 26;

    private boolean isEnd;

    // number of children non null links
    private int size;    
    public void put(char ch, TrieNode node) {
        links[ch -'a'] = node;
        size++;
    }

    public int getLinks() {
        return size;
    }
    //assume methods containsKey, isEnd, get, put are implemented as it is described
   //in  https://leetcode.com/articles/implement-trie-prefix-tree/)
}

public class Trie {

    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

//assume methods insert, search, searchPrefix are implemented as it is described
//in  https://leetcode.com/articles/implement-trie-prefix-tree/)
    private String searchLongestPrefix(String word) {
        TrieNode node = root;
        StringBuilder prefix = new StringBuilder();
        for (int i = 0; i < word.length(); i++) {
            char curLetter = word.charAt(i);
            if (node.containsKey(curLetter) && (node.getLinks() == 1) && (!node.isEnd())) {
                prefix.append(curLetter);
                node = node.get(curLetter);
            }
            else
                return prefix.toString();

         }
         return prefix.toString();
    }
}

// All solutions - https://leetcode.com/problems/longest-common-prefix/solution/