CareerCup

Algorithm:
1. Start i = 0.
2. If you find 0..i as a valid string.
3. Then at ith position, I need to recursively call the method and check if we get a word on the right hand side for the given left hand side of i. ie. 0..i substring is a valid word if and only if i+1..end can make a list of words successfully. Otherwise I would increment i.

I think this way we can get the solution

private List<String> findWordsInString(String fullString, int sIndex) {
		List<String> retList = null;
		int length = fullString.length();
		StringBuffer buffer = new StringBuffer();
		
		
		if (sIndex == length) return new Vector<String>();
		
		for (int i = sIndex; i < length; i++) {
			buffer.append(fullString.charAt(i));
			if (words.contains(buffer.toString())) {
				retList = new Vector<String>();
				
				List<String> recList = findWordsInString(fullString, i + 1);
				
				if (recList != null) {
					retList.add(buffer.toString());
					retList.addAll(recList);
				} else if (i == length - 1) {
					retList.add(buffer.toString());
				}
			}
		}
		
		
		return retList;
	}

The data structure you wanna consider here is Trie.

Assumption you gotto make.. is
1> you are provided with lexicon / dictionary
2> Enough Memory to construct Trie structure

Algo.

foreach character you read.
def word;
if by reading that char you can form a word return word
else word =+ char, clear(word);
end of for //

Now things to consider here is the approach as it is a good question of discussion.. like what is the approach longest fit or shortest fit word.. example "a" itself is a word yet it can be part of any word.

import java.util.ArrayList;

public class Sentence {

public static void main(String[] args) {
ArrayList<String> words = new ArrayList<String>();

words.add("this");
words.add("some");
words.add("is");
words.add("a");
words.add("sentence");
words.add("the");
words.add("an");

String string = "thisisasentence";

String out = "";

char[] strChar = string.toCharArray();

String temp = "";

for(int i = 0; i < strChar.length; i++) {
temp = temp + strChar[i];
if(words.contains(temp)) {
out = out + " " + temp;
temp = "";
}
}

System.out.println(out);

}
}

motivation can be taken from knowing how a compilor works.Scanner scan next charater from the input with carry look ahead of 1,now if current word is in dictionary add its position into stack with flag unresolved if carry look ahead can still make a word,use regex for you recue from the dictionary move next.case of This. but as we get after This it is i. so matching regex for thisi.* from dictionary will return negative hence backtract. For backup point use pop from stack. It will return the the end index of this,put space and continue continue with look ahead of one......

here i have used the map to check if the word exists in the dictionary, then I have used the backtracking to check if it forms the valid sentence by recursively calling for remaining string...

map<string,int>m;

bool checkifgood(string s, int start, int end, vector<string>& final)
{
    string ans ="";
    string temp = "";
    for(int j =start;j<=end;j++)
    {
        ans = ans + s[j];
    }
    //cout<<"here is "<<ans<<endl;
    if(m[ans]>0)
    {
        final.push_back(ans);
        return true;
    }
    else
    {
        int i;
        //cout<<"in else\n";
        for(i = start;i<=end;i++)
        {
            temp = temp + s[i];

            if(m[temp]>0)
             {
                 final.push_back(temp);
                 //cout<<"temp is "<<temp<<endl;
                 if(checkifgood(s,i+1,end,final))
                    return true;
                 else
                     final.pop_back();
            }
            else
                continue;
        }
        if(i==end+1)
            return false;
    }
    return false;
}



void function3()
{
    string s = "thereisman";
    vector<string>final;
    int l = s.size()-1;
    checkifgood(s,0,l,final);

    cout<<"size "<<final.size()<<endl;
    for(int i =0;i<final.size();i++)
    {
        cout<<final[i]<<" ";
    }
    cout<<endl;


}


int main()
{
    char s[] = "AbDeC";
    m["the"] = 1;
    m["there"] = 1;
    m["is"] = 1;
    m["an"] = 1;
    m["man"] = 1;
    function3();
    //swap(s[0],s[1]);
    //cout<<s<<endl;
    string a = "the";

    return 0;
}

I know of a recursive procedure. The whole string is to be processed one character at a time, by checking if the string processed so far is valid and the remaining unprocessed string recursively passed to the method. Dynamic programming using tables should yield better results.

I know of a recursive procedure. The whole string is to be processed one character at a time, by checking if the string processed so far is valid and the remaining unprocessed string recursively passed to the method. Dynamic programming using tables should yield better results.