CareerCup

public boolean isCriteriaSuccess( String s1) {
System.err.println( " Calling "+s1);
if ( s1 == null) return false;
if ( s1.length() == 1 ) return true;
if ( !inDict(s1)) return false;
System.err.println( " Calling recursively "+s1);
boolean retValue = false;
int strLength = s1.length();
for ( int i = 0;i < strLength ;i++) {
retValue = retValue || (isCriteriaSuccess(s1.substring(0,i)+s1.substring(i+1,strLength)));

}
return retValue;

}

If the number of query words is large and dictionary is static, here is what I propose:

Preprocessing:
Create a graph of all the dictionary words. Each word will get a node and there will be an edge between 2 nodes (or words) if one of the words is only one alphabet lesser than the other word. This should take O(M^2) time, but for practical purpose we can assume the number of words in dictionary are constant, so it could be assumed as a constant time preprocessing operation. (Note that M is the number of dictionary words)

Now to search if a word can be broken down to smaller words (until the word becomes null) do this:
1. Find the word in the graph. Let this node is called N(word). This step takes O(M) time where M is the number of dictionary words.
2. Do a depth first or breadth first traversal starting at N(word). You can stop traversing when you find a node with length zero and return True. (You'll only to traverse at most lengthOf(word) deep nodes from N(word)). If you couldn't reach a node with length 0, return False.
If L is the length of the query word, this step will take O(L*L) worst case time.

Java Implementation of remove word using dynamic programming...

public class RemoveWord {

	Map<String, Boolean> memorize;
	
	public RemoveWord() {
		super();
		memorize = new HashMap<String, Boolean>();
	}
	
	public boolean remove(String word, Set<String> dictionary) {
		if (word == null){
			return false;	
		}
		else if (word.length() == 1){
			return true;
		}
		else if (!dictionary.contains(word)){
			return false;
		}
		else {
			if(memorize.containsKey(word)){
				return memorize.get(word); 
			}
			else{
				boolean isValid = false;
				for ( int index = 0; index < word.length(); index++) {
					isValid = isValid || removeWord(word.substring(0, index)+ word.substring(index+1), dictionary);
				}
				memorize.put(word, isValid);
				return isValid;
			}
		}
	}

	public static void main(String[] args) {
		Set<String> dictionary = new HashSet<String>();
		dictionary.add("restated");
		dictionary.add("restate");
		dictionary.add("estate");
		dictionary.add("state");
		dictionary.add("stat");
		dictionary.add("sat");
		dictionary.add("at");
		
		RemoveWord obj = new RemoveWord();
		System.out.println(obj.remove("restated", dictionary));
	}	
}

Yes it can be done using dynamic programming. The problem here is not to check whether the word is in the dictionary or not. The problem is used to determine whether by taking out one alphabet at a time the remaining word is in the dictionary or not. Now this can be easily done by using dynamic programming or recursion. Here is the idea

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

bool dictionaryContains(string str)
{
     string dictionary[] = {"restated","restate","estate","state","stat","sat","at","a" };
    int size=sizeof(dictionary)/sizeof(dictionary[0]);
    for(int i=0;i<size;i++)
    {
        if(dictionary[i].compare(str)==0)
        {
                return true;
        }
    }
    return false;
}
bool wordBreak(string str,int temp)
{
    int size=str.size();
    if(size==0)
        return true;
    for(int i=1;i<=size;i++)
    {
        if(dictionaryContains(str.substr(0,temp))&&wordBreak(str.substr(0,temp-1)))
            return true;

    }
    return false;
}
int main()
{
    string str="restated";
    int n=str.size();
    if(wordBreak(str,n-1))
        cout<<"Can be broken";
    else
        cout<<"Cant be broken";
}

Just wanted to understand one thing. Isn't the requirement of the problem to check if each word formed by removal of a character is a word again?
i.e say ABCDxPQRS is a word. Then we need to confirm whether ABCDPQRS is a word or not? Similarly for other removals.
Right?

dict = ['restated','restate','estate','state','stat','sat','at','a']

def removeWords(string):
    l=[]
    for i in range(len(string)):
        ns = string[0:i]+string[i+1:]
        if ns in dict:
            l = l +[ns]
    return l


q = removeWords('restate')
size = len('restate')-1
flag = 0
while len(q)>0 and size > 1:
    qnew = []
    for a in q:
        qnew = qnew + removeWords(a)
    size = size -1
    if len(qnew)==0:
        flag = 1
        break;
    else:
        q = qnew


if flag=0 and size==1:
    print true

use dfs

import java.util.Arrays;
import java.util.List;

public class strCriteria {
public static void main(String args[])
{
String a="restat";
System.out.println(check(a,0,a.length()));
}
public static boolean findWord(String a)
{
List<String> st = Arrays.asList("restated","restate","estate","state","stat","tat","at","a");
if(st.contains(a))
return true;
return false;
}
public static boolean check(String a,int beg,int end)
{
if(beg>=end)
return true;
if(findWord(a.substring(beg, end)))
return check(a,beg+1,end) || check(a,beg,end-1);
return false;
}
}

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

int main(void)
{
char a[] = "restated";
unsigned int i, j;
char window[100];
vector<string> validWord; // will contains the vaid dictionary words

for(i = 1; i < strlen(a); i++)
{
for(j = 0; j <= strlen(a) - i; j++)
{
memcpy(window, a + j, i);
window[i] = 0;
if(IsInDictionary(window))
validWord.push_back(&window[i]);
}
}
return 0;
}

import java.util.HashSet;


public class RandomWord {

    public static void main(String[] args){

        String str = "restated";
        System.out.print(checkword(str));



    }
    public static boolean checkword(String str){

        if(str.length()==1)
            return true;

        for(int i=0;i<str.length();i++){

            String first = str.substring(0,i);
            String last = str.substring(i+1);
            String word = first+last;

            if(isValidWord(word)){
                System.out.println(word);
                if(checkword(word)){
                    return true;
                }else{
                    continue;
                }

            }


        }

        return false;
    }

    public static boolean isValidWord(String str){

        HashSet<String> wordSet = new HashSet<>();
        wordSet.add("restate");
        wordSet.add("estate");
        wordSet.add("state");
        wordSet.add("stte");
        wordSet.add("stat");
        wordSet.add("sat");
        wordSet.add("at");
        wordSet.add("a");

        return wordSet.contains(str);


    }

}

This can be done using DP

The recursion looks something like this:
Keep an index to the first and last char of the string say, beg and end

Now in every function call recurse using these two calls func(str, beg, end-1) and func(str, beg+1, end) , if beg==end return

int getSubWords(String str, int beg, int end) {
if(beg == end) {
return isWord(str.charAt(beg)) ;
}

return( isWord(str.substr(beg, end +1) + getSubWords(str, beg+1, end) + getSubstr(str, beg, end-1)));
}
This can be converted into DP by using a 2d memo array for keeping a count of the number of words found.

If I understand problem correctly, "sat" should not be the correct sub word of "restated".