Amazon Interview Question Software Engineer / Developers
Country: United States
This is not O(n^2) with the recursive call like this. Each of your recursive call is basically a for loop.
What is memorized for? And I don't think use recursion which return a string is suitable for this situation. There will be multiple answers rather than only one answer.
Well for each character in string.. the loop goes from its index to end of str... so basically the complexity is 0(n)*n = O(n^2) assuming the function isWord takes contant time.
you might want to solve this using trie. it will be easier to print the string for different substrings that might be present in the longer word. example "awe","some"--> "awesome".
you should add memoized.put at one more place
if (segSuffix != null) {
memoized.put(input, prefix + " " + segSuffix);
return prefix + " " + segSuffix;
}
DFS on the found words, when a solution (or a dead end) is found backtrack to the next alternative.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
/**
* O(n * w), where n is the length of the string and w is the number words in the string
*/
public class StringBreak {
public static void main(String[] args) {
Set<String> dict = new HashSet<String>();
dict.add("dog");
dict.add("cat");
dict.add("catalog");
dict.add("a");
dict.add("log");
dict.add("awesome");
dict.add("awe");
dict.add("some");
String[] s = breakString("dogcatalogawesome", dict);
System.out.println(Arrays.toString(s)); // dog cat a log awe some, dog cat a log awesome, dog catalog awe some, dog catalog awesome
}
static String[] breakString(String s, Set<String> dict) {
int i = 0;
List<String> ret = new ArrayList<String>();
Deque<StringBuilder> stack = new LinkedList<StringBuilder>();
stack.add(new StringBuilder());
while (!stack.isEmpty()) {
StringBuilder sb = stack.peekFirst();
sb.append(s.charAt(i));
if (dict.contains(sb.toString())) {
if (i == s.length() - 1) {
Iterator<StringBuilder> it = stack.descendingIterator();
StringBuilder result = new StringBuilder();
while (it.hasNext()) {
if (result.length() > 0) {
result.append(" ");
}
result.append(it.next().toString());
}
ret.add(result.toString());
} else {
stack.addFirst(new StringBuilder());
}
}
if (i < s.length() - 1) {
i++;
} else {
stack.removeFirst();
i = i - sb.length() + 1;
}
}
return ret.toArray(new String[ret.size()]);
}
}
this works :
public class word {
static Map<String, Boolean> dic = new HashMap<String, Boolean>();
static Map<String, String> map = new HashMap<String, String>();
static boolean isWord(String s) {
return dic.containsKey(s);
}
static void printWord(String s, String prev) {
if (isWord(s)) {
System.out.println(map.get(prev) + " " + s);
}
else if (map.containsKey(s)) {
if (!map.get(s).equals(""))
if (prev.equals(" "))
System.out.println(map.get(s));
else
System.out.println(map.get(prev) + " " + map.get(s));
}
int len = s.length();
for (int i = 1; i < len; i++) {
String prefix = s.substring(0, i);
if (isWord(prefix)) {
map.put(prev + prefix, map.get(prev) + " " + prefix);
String suffix = s.substring(i);
printWord(suffix, prev + prefix);
} else
map.put(prev + prefix, "");
}
}
public static void main(String[] args) {
map.put("", "");
dic.put("this", true);
dic.put("is", true);
dic.put("awesome", true);
dic.put("some", true);
dic.put("awe", true);
printWord("thisisawesome","");
}
}
Given the dictionary function isWord(String) and a input string (without space) such as the one in the question, generate the output as described in the question.
This is my solution. Because I cannot test my code, maybe there are some problems.
static HashMap<String,Boolean> map=new HashMap<String,Boolean>();
static List<String> strList=new ArrayList<String>();
public static void findWord(String str, String prestr){
for(int i=1;i<str.length();i++){
boolean isw=false;
String segement=str.substring(0,i+1);
if(map.containsKey(segement)){
isw=map.get(str);
}else{
isw=dict.isWord(str);
map.put(str,isw);
}
if(isw){
String completeString= prestr+" "+str;
if(i<str.length()-1){
String secondstr=str.substring(i+1,str.length());
findWord(secondstr,completeString);
}else{
strList.add(completeString);
}
}
}
}
Tested and working fine.... Tree used to get multiple possiblites and to handle ambiguity
package com.algorithm;
import java.util.TreeSet;
import javax.swing.tree.DefaultMutableTreeNode;
import javax.swing.tree.DefaultTreeModel;
public class SegmentWord {
private static TreeSet<String> dict = new TreeSet<String>();
static {
dict.add("this");
dict.add("is");
dict.add("awesome");
dict.add("awe");
dict.add("some");
}
public static DefaultTreeModel treemodel = new DefaultTreeModel(null);
private boolean searchNode(String input, DefaultMutableTreeNode parent) {
if(null == parent || null == input)
return false;
DefaultMutableTreeNode child;
int childCount = parent.getChildCount();
for (int i = 0; i < childCount; i++) {
child=(DefaultMutableTreeNode)parent.getChildAt(i);
if(input.equals(child.getUserObject()) || searchNode(input, child))
return true;
}
return false;
}
private DefaultMutableTreeNode addNode(DefaultMutableTreeNode parent, String input) {
DefaultMutableTreeNode child = new DefaultMutableTreeNode(input);
if(null == parent) {
treemodel.setRoot(child);
} else {
parent.add(child);
}
return child;
}
public void printTree(DefaultMutableTreeNode node) {
int childCount = node.getChildCount();
if(0==childCount) {
String path[]=new String[node.getUserObjectPath().length];
System.arraycopy(node.getUserObjectPath(), 0, path, 0, node.getUserObjectPath().length);
for (String ptr : path)
System.out.print(ptr + " ");
System.out.println();
return;
}
for(int i=0; i<childCount; i++) {
printTree((DefaultMutableTreeNode)node.getChildAt(i));
}
}
public void SegmentString(String input, DefaultMutableTreeNode parent) {
if (searchNode(input, (DefaultMutableTreeNode)treemodel.getRoot())) {
addNode(parent, input);
return;
}
int len = input.length();
for (int i = 1; i <= len; i++) {
String prefix = input.substring(0, i);
if (dict.contains(prefix)) {
DefaultMutableTreeNode newChild = addNode(parent, prefix);
String suffix = input.substring(i, len);
SegmentString(suffix, newChild);
}
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
SegmentWord segmentWord = new SegmentWord();
segmentWord.SegmentString("thisisawesome", null);
segmentWord.printTree((DefaultMutableTreeNode)treemodel.getRoot());
}
}
I wrote the following code, hope to help u. it's just a simple dfs
public static void string_decomposition(String s, int charIndex, ArrayList<String> list,Set<String>set){
if(charIndex == s.length()){
System.out.println(Arrays.toString(list.toArray()));
return;
}
for(int i=0;i< s.length();i++){
if(set.contains(s.substring(0, i+1))){
list.add(s.substring(0, i+1));
if(i==s.length()-1){
System.out.println(Arrays.toString(list.toArray()));
return;
}
string_decomposition(s.substring(i+1,s.length()), i+1, list, set);
list.remove(s.substring(0, i+1));
}
}
}
public static void main(String[] args) throws Exception {
HashSet<String> s = new HashSet<String>();
s.add("this");
s.add("is");
s.add("awesome");
ArrayList<String> list = new ArrayList<String>();
string_decomposition("thisisawesome", 0, list, s);
}
Assume the dictionary is stored as a TRIE and has the following functions:
bool isPotentialWord(String str)
e.g. "qs" will return false since no word starts with qs
"ca" will return true as "cat", "category", "cast" etc.... are words
bool isWord(String str)
will return true if given word is a string
List<String> allPotentialStrings(String inputStr)
{
if(String.IsEmpty(inputStr))
return null;
return allPotentialStrings(inputStr, 0);
}
List<String> allPotentialStrings(String inputStr, int startIndex)
{
if(startIndex > inputStr.length - 1)
return ".";
List<String> outputStr = new List<String>();
String currStr = "";
for(int index = startIndex; index < inputStr.length; ++index)
{
currStr += ch;
if(!isPotentialWord(currStr))
break;
else if(!isWord(currStr))
continue;
else
{
List<String> restStr = allPotentialStrings(inputStr, index + 1);
if(null == restStr)
continue;
foreach(String str in restStr)
outputStr.add(currStr + " " + str);
}
}
return outputStr;
}
Map<String, String> memoized; String SegmentString(String input, Set<String> dict) { if (dict.isWord(input)) return input; if (memoized.containsKey(input) { return memoized.get(input); } int len = input.length(); for (int i = 1; i < len; i++) { String prefix = input.substring(0, i); if (dict.isWord(prefix)) { String suffix = input.substring(i, len); String segSuffix = SegmentString(suffix, dict); if (segSuffix != null) { return prefix + " " + segSuffix; } } memoized.put(input, null); return null; }Time complexity : O(n^2) Supposing that substring operation only requires constant time.
- Nitin Gupta November 08, 2012