Created
March 5, 2012 11:30
-
-
Save eugenp/1977943 to your computer and use it in GitHub Desktop.
Interview Question:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.macys.rest.common; | |
import java.util.HashSet; | |
import java.util.Set; | |
/** | |
* - link: http://thenoisychannel.com/2011/08/08/retiring-a-great-interview-problem/ <br> | |
* Given an input string and a dictionary of words, segment the input string into a space-separated sequence of dictionary words if possible. | |
* For example, if the input string is "applepie" and dictionary contains a | |
* standard set of English words, then we would return the string "apple pie" as output. | |
* You don't need to implement the dictionary. Just assume access to a reasonable implementation. | |
*/ | |
public class Q { | |
private static Set<String> dictionary = new HashSet<String>(); | |
static { | |
dictionary.add("this"); | |
dictionary.add("text"); | |
dictionary.add("is"); | |
dictionary.add("short"); | |
dictionary.add("shorter"); | |
} | |
// | |
public static void main(final String[] args) { | |
final String arg0 = "thistextisshorter"; // | |
System.out.println(sol1(arg0)); | |
System.out.println(sol2(arg0)); | |
System.out.println(sol3(arg0)); | |
System.out.println(sol4(arg0)); | |
} | |
// | |
/** | |
* - not fully working | |
*/ | |
public static String sol1(final String input) { | |
StringBuilder result = new StringBuilder(); | |
StringBuilder b = new StringBuilder(); | |
for (int i = 0; i < input.length(); i++) { | |
b.append(input.charAt(i)); | |
if (dictionary.contains(b.toString())) { | |
result.append(b); | |
result.append(" "); | |
b = new StringBuilder(); | |
} | |
} | |
return result.toString(); | |
} | |
/** | |
* - note: not working | |
*/ | |
public static String sol2(final String input) { | |
int len = input.length(); | |
for (int i = 0; i < len; i++) { | |
String prefix = input.substring(0, i); | |
if (dictionary.contains(prefix)) { | |
String suffix = input.substring(i, len); | |
if (dictionary.contains(suffix)) { | |
return prefix + " " + suffix; | |
} | |
} | |
} | |
return null; | |
} | |
/** | |
* - note: recursive | |
*/ | |
public static String sol3(final String input) { | |
if (dictionary.contains(input)) { | |
return input; | |
} | |
int len = input.length(); | |
for (int i = 1; i < len; i++) { | |
String prefix = input.substring(0, i); | |
if (dictionary.contains(prefix)) { | |
String suffix = input.substring(i, len); | |
String segSuffix = sol3(suffix); | |
if (segSuffix != null) { | |
return prefix + " " + segSuffix; | |
} | |
} | |
} | |
return null; | |
} | |
/** | |
* - note: recursive | |
*/ | |
public static String sol4(final String input) { | |
if (dictionary.contains(input)) { | |
return input; | |
} | |
final int len = input.length(); | |
for (int i = 1; i < len; i++) { | |
// System.out.println( "Outer; i=" + i ); | |
final String prefix = input.substring(0, i); | |
if (dictionary.contains(prefix)) { | |
// System.out.println( "In" ); | |
final String result = prefix + " " + sol4(input.substring(i, len)); | |
// System.out.println( "Out" ); | |
return result; | |
} | |
} | |
return null; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment