Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words. You need to output the minimum number of words.

For example,

input: "aaaisaname"
dict: ("a", "aaa", "is", "name")

output: "aaa is a name"

Wrong output: "a a a is a name"

Question

Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words. You need to output the minimum number of words. 

For example, 

input: "aaaisaname" 
dict: ("a", "aaa", "is", "name") 

output: "aaa is a name" 

Wrong output: "a a a is a name"

Sigiloso · Accepted Answer

int minCut(String s, Set dict) {
        int n = s.length();
        int[] cut = new int[n];
        
        for(int i = 0;i0)
                    {
                        cut[i] = Math.min(cut[i],cut[j-1]+1);
                    }
                    else cut[i] = 0;
                }
            }
        }
        return cut[n-1];
    }

Sigiloso · Answer

int n = s.length();
        int[] cut = new int[n];
        
        for(int i = 0;i0)
                    {
                        cut[i] = Math.min(cut[i],cut[j-1]+1);
                    }
                    else cut[i] = 0;
                }
            }
        }
        int min = 0,idx  = 0;
        for(int i = 1;i

Sigiloso · Answer

Knapsack problem solvable with DP.

Sigiloso · Answer

search for word break problem; many different solutions.

Sigiloso · Answer

// here's a recursive solution  (note that after returning, you're required to reverse the arraylist (for this imp.)
public static ArrayList method (String str, String curString, ArrayList dict) {
		if (str.length() == 0) {
		    return new ArrayList();
		}
		int pointerIndex = 0;
		ArrayList result;
		 if (dict.contains(curString + str.charAt(pointerIndex))) {
		   // Either take this current character and try to keep going, or ditch it and add it to the arraylist
		  ArrayList first = method(str.substring(1), curString + str.charAt(pointerIndex), dict);
		  ArrayList second = method(str.substring(1), "", dict );
			second.add(dict.get(dict.indexOf(curString+str.charAt(pointerIndex))));

			// if the size is 0,  don't consider it, otherwise, if the sizes are nonzero, take the one with less
			if (first.size() == 0 || second.size() == 0) {
				result = (first.size() == 0) ? second : first;
			} else {
				result = (first.size() > second.size()) ? second : first;
			}
		} else {
		  // here we're forced to take the next character
		  result = method(str.substring(1), curString + str.charAt(pointerIndex), dict);
		}
		return result;
	}

I don't think this recursive is that good though... I can't see how to make it a dp :(

Pinterest

Pergunta de entrevista da empresa Pinterest

Respostas da entrevista

Empresas seguidas

Buscas de vagas