Write a function to find the longest common prefix string amongst an array of strings

Simple Algorithm Will Go Like This:

Algorithm:Longest Common Prefix ( LCP)

1.Take a String From Array Whose length is Minimum else

  you might get exception if tries to access array element

  outside range.why this will work because if there exist 

  a common prefix then it will be the desired answer .

 Example like in case of "shash" ,"shank","shashank" LCP will be "sha"

 for this string "ab", "abc", "def" ,"defgh", "sha" LCP will be NULL

2.Keep Comparing reamining string character by character with 1st selected string  if mismatch occurs at any position i then append 1st string to output string.

Working Code

String findLongPrefix(String [] str) 

{
                StringBuilder strBuilder = new StringBuilder();
                
                char [] firstStr = str[0].toCharArray();
                for(int i=0; i< str[0].length(); i++ ) {
                        boolean found = true;
                        for(String str: str) {
                                if(str.charAt(i) != firstStr[i]) {
                                        found = false;
                                        break;
                                } 
                        }
                        
                        if(found) {
                                strBuilder.append(firstStr[i]);
                        } else 
                                break;
                        
                }
                
                return strBuilder.toString();
        }

Time Complexity O(N*M-1)=O( Where N is Length of 1st Smallest String 

and M is Number of remaining string in string array so it will run

upto length of array-1

Space Complexity O(1)

Design An Algorithm to Exhibit Did You Mean Feature of Google Search Engine

When people search at Google, they often type two words without space. For example, instead of typing "binary tree", someone can type "binarytree". Given an input, what is a good way of finding if it is a combination of two valid words e.g. In Directly You have Add Space between two such or if are using some data structure , whene words would have been inserted , you would have mainted a boolen varible to defined the end of word (eod)


An Exanmple Will be Let's say you have a phrase without any spaces - eg. "thisisawesome". Given a dictionary, how would you add spaces in this string?

When people search at Google, they often type two words without space. For example, instead of typing "binary tree", someone can type "binarytree". Given an input, what is a good way of finding if it is a combination of two valid words e.g. In Directly You have Add Space between two such or if are using some data structure , where words would have been inserted , you would have maintained a boolean variable to defined the end of word (eod)
An Example Will be Let's say you have a phrase without any spaces - eg. "thisisawesome". Given a dictionary, how would you add spaces in this string?

        Trie trie = new Trie();
        trie.insert("i");
        trie.insert("this");
        trie.insert("saw");
        trie.insert("is");
        trie.insert("a");
        trie.insert("some");
        trie.insert("awesome");

        String inputString = "thisisawesome";
        String outputString = "";
      
        int left = 0;
        int right = 1;

        while ( right <= inputString.length()) 

        {
            {
                String str = inputString.substring(left,right);
                boolean found = trie.containsKey(str);
                if ( found) 

                {
                    outputString += str;
                    outputString += " ";
                    left += str.length();
                    right = left + 1;
                }

                 else

                 {
                    right++;
                }
            }
        }
      
   

Another Good Working Code  You Can Refer Avinash Solution


Time Complexity O(K) k is length of input string

Given a list of Tagalog words as a String[], return the same list in Tagalog alphabetical order

A Reader send me this problem . Thanks to Him for this intersteing Problem. so i am going to posting here.

In the first half of the 20th century, around the time that Tagalog became the national language of the Philippines, a standardized alphabet was introduced to be used in Tagalog school books (since then, the national language has changed to a hybrid "Pilipino" language, as Tagalog is only one of several major languages spoken in the Philippines).

Tagalog's 20-letter alphabet is as follows:

a b k d e g h i l m n ng o p r s t u w y

Note that not all letters used in English are present, 'k' is the third letter, and 'ng' is a single letter that comes between 'n' and 'o'.

You are compiling a Tagalog dictionary, and for people to be able to find words in it, the words need to be sorted in alphabetical order with reference to the Tagalog alphabet. Given a list of Tagalog words as a String[], return the same list in Tagalog alphabetical order

1)


{"ang","ano","anim","alak","alam","alab"}

Returns: {"alab", "alak", "alam", "anim", "ano", "ang" }

A few "A" words that are alphabetically close together.
2)


{"siya","niya","kaniya","ikaw","ito","iyon"}

Returns: {"kaniya", "ikaw", "ito", "iyon", "niya", "siya" }

Common Tagalog pronouns.
3)


{"kaba","baka","naba","ngipin","nipin"}

Returns: {"baka", "kaba", "naba", "nipin", "ngipin" }