在整理计算机时，发现某某公司一道算法面试题，原题找不到了，只找出来注释和算法，发出来大家探讨下.
Given a valid sentence without any spaces between the words and a dictionary of valid English words, find all possible ways to break the sentence in individual dictionary words.
public List<String> searchWord(String testWord, String[]... dictionarys) {
List<String> dictionaryList = new ArrayList<String>();
for(String[] array : dictionarys)
{
dictionaryList.addAll(Arrays.asList(array));
}
List<String> listAllDistinct = dictionaryList.stream().distinct().collect(Collectors.toList());
Node root = null;
Node node = null;
int slength = testWord.length() + 1;
boolean[] stauts = new boolean[slength];
Queue<Integer> queue = new LinkedList<Integer>();
Utils.getStartIndex(queue, root);
int size = 0;
while (!queue.isEmpty()) {
size = queue.size();
for (int i = 0; i < size; i++) {
int startPosition = queue.poll().intValue();
for (String word : listAllDistinct) {
int endIndex = startPosition + word.length();
if (endIndex > slength) {
continue;
} else if (endIndex == slength) {
endIndex = endIndex - 1;
}
String result = testWord.substring(startPosition, endIndex);
if (!result.equals(word)) {
continue;
}
stauts[startPosition] = true; // hit or not hie while the and
node = new Node(startPosition, endIndex, result);
root = Utils.addNode(root, node);
}
// while finish it is need hit
if (startPosition == slength - 1) {
stauts[startPosition] = true;
}
if (!stauts[startPosition]) {
if (null == root)
{
root = new Node(0, -1, "");
}else
{
Utils.deleteNode(startPosition, root);
}
}
}
if (!stauts[slength - 1]) {
Utils.getStartIndex(queue, root);
}
}
List<String> checkResultList = new ArrayList<String>();
Utils.outString(new StringBuffer(""), root, checkResultList);
return checkResultList;
}
public class Utils {
public static Node addNode(Node root, Node node) {
if (null == root) {
root = node;
} else {
addChildNode(root, node);
}
return root;
}
public static void addChildNode(Node root, Node node) {
if(root.getEndIndex() == node.getStartIndex())
{
if (null == root.getChildNode()) {
List<Node> nlist = new ArrayList<Node>();
root.setChildNode(nlist);
root.add(node);
} else{
boolean isAdd = true;
for(Node child : root.getChildNode())
{
if (child.getStartIndex() == node.getStartIndex() && child.getEndIndex() == node.getEndIndex() &&
child.getWord().equals(node.getWord()))
{
isAdd = false;
break;
}
}
if (isAdd)
{
root.getChildNode().add(node);
}
}
} else if(null != root.getChildNode()){
for (Node child : root.getChildNode()) {
addChildNode(child, node);
}
}
}
public static Queue<Integer> getStartIndex(Queue<Integer> queue, Node node) {
if (null == node) {
queue.add(0);
} else if (null == node.getChildNode()) {
if (node.getEndIndex() != -1) {
queue.add(node.getEndIndex());
}
} else {
for (Node childNode : node.getChildNode()) {
getStartIndex(queue, childNode);
}
}
return queue;
}
public static void deleteNode(int deleteIndex, Node root) {
if (deleteIndex == root.getEndIndex()) {
root = null;
} else if (null != root.getChildNode()) {
Iterator<Node> iterator = root.getChildNode().iterator();
while (iterator.hasNext()) {
Node childNode = iterator.next();
if (deleteIndex == childNode.getEndIndex()) {
iterator.remove();
}else
{
deleteNode(deleteIndex, childNode);
}
}
}
}
public static void outString(StringBuffer sb, Node node, List<String> listBuffer) {
if (null == node.getChildNode()) {
sb.append(" " + node.getWord());
listBuffer.add(sb.delete(0, 1).toString());
} else {
sb.append(" " + node.getWord());
for (Node childNode : node.getChildNode()) {
outString(new StringBuffer(sb), childNode, listBuffer);
}
}
// return sb.toString();
}
}
public class Node{
private int startIndex;
private int endIndex;
private String word;
private List<Node> nextNode = null;
public Node(int startIndex, int endIndex, String word)
{
this.startIndex = startIndex;
this.endIndex = endIndex;
this.word = word;
}
public void add(Node node){
nextNode.add(node);
}
public int getStartIndex() {
return startIndex;
}
public void setStartIndex(int startIndex) {
this.startIndex = startIndex;
}
public int getEndIndex() {
return endIndex;
}
public void setEndIndex(int endIndex) {
this.endIndex = endIndex;
}
public String getWord() {
return word;
}
public void setWord(String word) {
this.word = word;
}
public List<Node> getChildNode() {
return nextNode;
}
public void setChildNode(List<Node> nextNode) {
this.nextNode = nextNode;
}
}
测试代码：
@Test
public void testString1UseDictionary1() {
WordBreak codeTest = new WordBreak();
String[] dictionary = { "i", "like", "sam", "sung", "samsung", "mobile", "ice", "cream", "and", "man", "go" };
String str = "ilikesamsungmobile";
List<String> result = codeTest.searchWord(str, dictionary);
String[] array = { "i like sam sung mobile", "i like samsung mobile" };
Assert.assertArrayEquals(array, result.toArray());
}
@Test
public void testString2UseDictionary1() {
WordBreak codeTest = new WordBreak();
String[] dictionaryArray = { "i", "like", "sam", "sung", "samsung", "mobile", "ice", "cream", "and", "man",
"go" };
String str = "ilikeicecreamandmango";
List<String> result = codeTest.searchWord(str, dictionaryArray);
String[] array = { "i like ice cream and man go" };
Assert.assertArrayEquals(array, result.toArray());
}
@Test
public void testUserDictionary1() {
WordBreak codeTest = new WordBreak();
String[] dictionary = { "i", "like", "sam", "sung", "mobile", "icecream", "and", "man go", "mango" };
String str = "ilikeicecreamandmango";
List<String> result = codeTest.searchWord(str, dictionary);
String[] array = { "i like icecream and mango" };
Assert.assertArrayEquals(array, result.toArray());
}
@Test
public void testUserDictionary2() {
WordBreak codeTest = new WordBreak();
String[] dictionary = { "i", "like", "sam", "sung", "mobile", "icecream", "and", "man", "go", "mango" };
String str = "ilikeicecreamandmango";
List<String> result = codeTest.searchWord(str, dictionary);
String[] array = { "i like icecream and man go", "i like icecream and mango" };
Assert.assertArrayEquals(array, result.toArray());
}
@Test
public void testDoubleDictionary() {
WordBreak codeTest = new WordBreak();
String[] dictionary1 = { "i", "like", "sam", "sung", "samsung", "mobile", "ice", "cream", "and", "man", "go" };
String[] dictionary2 = { "i", "like", "sam", "sung", "mobile", "icecream", "and", "man", "go", "mango" };
String str = "ilikeicecreamandmango";
List<String> result = codeTest.searchWord(str, dictionary1, dictionary2);
String[] array = { "i like ice cream and man go", "i like ice cream and mango", "i like icecream and man go",
"i like icecream and mango" };
Assert.assertArrayEquals(array, result.toArray());
}
@Test
public void testWithoutHit() {
WordBreak codeTest = new WordBreak();
String[] dictionary1 = { "our", "me", "summer", "song" };
String str = "ilikeicecreamandmango";
List<String> result = codeTest.searchWord(str, dictionary1);
String[] array = { "" };
Assert.assertArrayEquals(array, result.toArray());
}
@Test
public void testHalfHit() {
WordBreak codeTest = new WordBreak();
String[] dictionary1 = { "i", "like", "ice" };
String str = "ilikeicecreamandmango";
List<String> result = codeTest.searchWord(str, dictionary1);
String[] array = {};
Assert.assertArrayEquals(array, result.toArray());
}