在整理计算机时，发现某某公司一道算法面试题，原题找不到了，只找出来注释和算法，发出来大家探讨下.

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());	}