Yijie Li
BAN USERthis 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","");
}
}
I think we can do it in nlogn by first sorting it, then check if a[i-1]+a[i]+a[i+1] is in range(1,2) from i=(1 to lastIndex-1)
- Yijie Li February 18, 2013