CareerCup

I'd use a trie build from the list of given words. Start from the given string such as "mobilelg" Look for a complete word. When found split the word and start from the found index. eg if mobile is in the dictionary trie, start from index 5 from the root of the trie. repeat until all the chars covered or not found.

This question you asked is from flipkart's interview street coding round....
You can find the correct solution at geeks for geeks... There search for split sentence (using dynamic programming) . solution there needs a little modification to print the split up words and also you need to add condition to check if sub string of a string and the string both lie in dictionary. This case is not covered in any solution found over net.

There is one more requirement / property that algorithm should satisy which I missed in above question :
4. If there is no match based on mentioned 3 properties / requirements, then output should be "NULL". For eg.,

Assume you are given the following list of words : mobile, flip, kart, flipkart and user-input query string is flipkartmobilenotpresent. In this case, the answer / output should be "NULL" as no split-up is possible based on given dictionary words.

I implemented it using the following algorithm :
1. For each dictionary word, find the index of all occurences in query string (could be repetitions of dictionary words in query string as explained). Add this index and corresponding word in a map.

2. After this, there will be a map with indexes of all occuring dictionary words in query string.

3. Iterate through map (since map will have its keys sorted in C++) take each word and concatenate it. If the result of concatenation is not query string then, output "NULL".

At the same time, concatenate each word from map with space. In the event that result from above equals query string, then output this concatenation of words with spaces.

Following is the code snippet :

#include <iostream>
#include <deque>
#include <string>
#include <map>

namespace
{
    static const size_t& MAX_QUERY_LENGTH(500);
}

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    std::size_t dict_size;
    std::deque<std::string> dict;
    std::string query;
    std::string output("NULL");

    // read input
    std::cin >> dict_size;
    for(std::size_t i(0); i < dict_size; ++i)
    {
        std::string word;
        std::cin >> word;
        dict.push_back(word);
    }

    // limit query string to allowed MAX_QUERY_LENGTH
    std::cin >> query;
    if(query.size() > MAX_QUERY_LENGTH)
    {
        query.erase(MAX_QUERY_LENGTH);
    }

    std::map<std::size_t, std::string> index_word_map;
    for(std::deque<std::string>::const_iterator dict_iter(dict.begin()), dict_end(dict.end()); dict_iter != dict_end; ++dict_iter)
    {
        std::string::size_type pos(0);
        for(;(pos = query.find(*dict_iter, pos)) != std::string::npos;)
        {
            std::map<std::size_t, std::string>::iterator iwm_iter(index_word_map.find(pos));
            if(iwm_iter == index_word_map.end())
            {
                index_word_map.insert(std::make_pair<std::string::size_type, std::string>(pos, *dict_iter));
            }
            else
            {
                std::string& word(iwm_iter->second);
                if(word.size() > dict_iter->size())
                {
                    word = *dict_iter;
                }
            }

            pos += dict_iter->size();
        }
    }

    std::string present, splitup;
    for(std::map<std::size_t, std::string>::iterator iwm_iter(index_word_map.begin()),
        iwm_end(index_word_map.end()); iwm_iter != iwm_end; ++iwm_iter)
    {
        present += "" + iwm_iter->second;
        splitup += iwm_iter->second + " ";
    }

    if(present == query)
    {
        output = splitup;
    }

    std::cout << output;

    return 0;
}

/**
 * Logic is
 * Process the dictionary into trie
 * String[] array = {"Flip","Kart","Mobile","lc"};
 * to trie
 *
 * Process the queryString "flipkartmobile" as mentioned below
 * f
 * fl
 * fli
 * flip
 * k
 * ka
 * kar
 * kart
 * m
 * mo
 * mob
 * mobi
 * mobil
 * mobile
 *
 *If there is a match add it to targetString and append one tab
 *
 * i/p : flipkartmobile
 * o/p : flip	kart	mobile	
 *
 * i/p : flipkartmobilelclc
 * o/p : flip	kart	mobile	lc	lc
 */

public class KartExample {
    public KartExample() {
        super();
    }

    public static void main(String[] args) {
        KartExample kartExample = new KartExample();
        String[] array = { "Flip", "Kart", "Mobile", "lc" };
        KartExample.Trie trie = kartExample.new Trie();
        for (String str : array) {
            trie.insert(str);
        }
        String queryString = "flipkartmobilelclc";
        int j = 0;
        boolean find = false;
        String targetString = "";
        if (queryString.length() < 500) {
            for (int i = 0; i < queryString.length(); i++) {
                //            System.out.println(queryString.substring(j,i+1));
                find = trie.search(queryString.substring(j, i + 1));
                if (find) {
                    targetString = targetString + queryString.substring(j, i + 1) + "\t";
                    j = i + 1;
                }
            }
            System.out.println(targetString);
        }
    }

    class Trie {
        private Trie[] trieArray;
        private char data;
        private int now;
        private boolean word;
        private Trie root;

        public Trie() {
            this.setData(' ');
            this.setTrieArray(new Trie[26]);
        }

        public Trie(char data) {
            this.setData(data);
            this.setTrieArray(new Trie[26]);
        }

        public boolean search(String pattern) {
            Trie root = this.getRoot();
            if (this.getRoot() == null) {
                return false;
            }
            for (int i = 0; i < pattern.length(); i++) {
                if (root.getTrieArray()[atoi(pattern.charAt(i))] == null) {
                    return false;
                }
                root = root.getTrieArray()[atoi(pattern.charAt(i))];
            }
            return root.isWord();
        }

        public void insert(String item) {
            Trie root = this.getRoot();
            if (this.getRoot() == null) {
                root = new Trie();
                this.setRoot(root);
            }
            for (int i = 0; i < item.length(); i++) {
                if (root.getTrieArray()[atoi(item.charAt(i))] == null) {
                    root.getTrieArray()[atoi(item.charAt(i))] = new Trie(item.charAt(i));
                }
                root = root.getTrieArray()[atoi(item.charAt(i))];
            }
            root.setWord(true);
            root.setNow(root.getNow() + 1);

        }

        public int atoi(char ch) {
            int i = 0;
            if (ch >= 65 && ch <= 90)
                i = ch - 65;
            else if (ch >= 97 && ch <= 122)
                i = ch - 97;
            else
                i = (int)ch;
            return i;

        }


        public void setTrieArray(Trie[] trieArray) {
            this.trieArray = trieArray;
        }

        public Trie[] getTrieArray() {
            return trieArray;
        }

        public void setData(char data) {
            this.data = data;
        }

        public char getData() {
            return data;
        }

        public void setNow(int now) {
            this.now = now;
        }

        public int getNow() {
            return now;
        }

        public void setWord(boolean word) {
            this.word = word;
        }

        public boolean isWord() {
            return word;
        }

        public void setRoot(Trie root) {
            this.root = root;
        }

        public Trie getRoot() {
            return root;
        }
    }

}

Following Code works perfectly:

public class SplitWords {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		String[] dict={"jungleegames","that","what","is"};
		String query="thatjungleegameswhatisthat";
		String query1;
		int index;
		int beginIndex=0;
		for(String s: dict){
			if(query.contains(s)){
			beginIndex=query.indexOf(s);
			index=beginIndex+s.length();
			System.out.println("BeginIndex=" + beginIndex + " " + s+ " Index=" + index);
			
				query1=query.substring(beginIndex,index);
				if(beginIndex!=0){
					
				
					
					query= query.substring(0,beginIndex)+ query1 + " " + query.substring(index);
					beginIndex=index;
				}
					else
					{
						query=query1+" " +  query.substring(index);
					}
			//	beginIndex=index;
			
		}
		
	}
		
		System.out.println(query);
	}
}

This is not gona work. Lets suppose ur input is thatjungleegameswhatisthatwhat. you code will divide by that jungleegames what is thatwhat. Repetition of words not handled.
Also what if i add "flipper, flip" to dictionary and string is flipper. You will divide it as "flip per"

why we are not solving this problem by storing dictionary words in reverse order (in trie) and check input query string from last charecter..

suppose Dictionary words are Dictionary words: flip, flipper, dolphin
input String is : flipperdolphin

it will get stored in trie in following manner
pilf,reppilf,nihplod.

if we check in reverse order first it will found 'dolphin' then 'flipper'.

#include <iostream>
using namespace std;
#include <vector>
#include <map>
#include <set>
#include <string>


void PopulateDictionary(std::set<string>& dict)
{
dict.insert("ab");
dict.insert("ba");
dict.insert("abab");
dict.insert("baba");
dict.insert("Flip");
dict.insert("kart");
dict.insert("Flipkarted");
dict.insert("Mobile");
dict.insert("A");
dict.insert("Apple");
dict.insert("Pie");
dict.insert("i");
}
typedef std::vector<string> StringVec;
bool FindPossibleWords(unsigned int strRemaining, unsigned int strSize, std::map<int, std::vector<string>>& HashMap, StringVec& strVec)
{
if (strRemaining == strSize)
return true;
if (HashMap.find(strRemaining) == HashMap.end())
return false;
StringVec words = HashMap[strRemaining];
for (unsigned int i = 0; i < words.size(); i++)
{
if (FindPossibleWords(words[i].size() + strRemaining,
strSize,
HashMap, strVec))
{
strVec.insert(strVec.begin(), words[i]);
return true;
}
}
return false;
}
int main()
{
string str("ApplePie");
unsigned int strSize = str.size();
std::set<string> dict;
std::map<int, std::vector<string>>HashMap;

PopulateDictionary(dict);


for (unsigned int i = 0; i < strSize; i++)
{
for (unsigned int j = i + 1; j < strSize; j++)
{
string sub = str.substr(i,j-i+1);
if (dict.find(sub) != dict.end())
{
//insert in hash map
HashMap[i].push_back(sub);
}
}
}

StringVec finalWords;
bool found = FindPossibleWords(0, strSize, HashMap, finalWords);
if (found)
{
for (unsigned int i = 0; i < finalWords.size(); i++)
cout<<finalWords[i]<<endl;
}
else
{
cout<<"No appropriate word was found\n";
}

return 0;
}

Its worked for me:

public static string ChangeInputString(string searchKeyword = "flipkartmobilesearch")
{
string modifiedSearchKey = string.Empty;
Dictionary<string, string> keywords = new Dictionary<string, string>();
keywords.Add("search", "search");
keywords.Add("flip", "flip");
keywords.Add("kart", "kart");
keywords.Add("mobile", "mobile");
keywords.Add("dummy", "dummy");
Dictionary<string, string> tempkeywords = keywords;

for (int i = 0; i < tempkeywords.Keys.Count && searchKeyword.Length>0; i++)
{
var item = tempkeywords.ElementAt(i);
if (searchKeyword.StartsWith(item.Value))
{
searchKeyword=searchKeyword.Substring(item.Value.Length, searchKeyword.Length-item.Value.Length);
modifiedSearchKey = modifiedSearchKey+item.Value + " ";
tempkeywords.Remove(item.Key.ToString());
i = -1;
}
}
return modifiedSearchKey.TrimEnd();//flip kart mobile search
}