学步园

题目

原文：

Write a program to find the longest word made of other words.

译文： 

写一个程序找出由其他单词组成的最长的单词。

解答

首先将单词按照长度的大小降序排序（重写比较器），再不断地取单词的前缀s，当s存在于单词数组中，递归调用该函数， 判断剩余串是否可以由其它单词组成。如果可以，返回true。

代码如下：

import java.util.ArrayList;  
import java.util.Arrays;  
import java.util.Comparator;  
import java.util.HashMap;  

class Q20_7{
	public static void main(String[] args){
		String[] arr = createGiantArray();  
        printLongestWord(arr);
	}

	static class LengthComparator implements Comparator<String>{
		public int compare(String o1,String o2){
			return o2.length()-o1.length();
		}
	}

	public static String printLongestWord(String[] arr){
		HashMap<String,Boolean> map=new HashMap<String,Boolean>();
		for(String str:arr){
			map.put(str,true);
		}
		Arrays.sort(arr,new LengthComparator());

		for(String s:arr){
			if(canBuildWord(s,true,map)){
				System.out.println(s);
				return s;
			}
		}
		return "";
	}

	// DFS深搜  
	public static boolean canBuildWord(String str,boolean isOriginalWord,HashMap<String,Boolean> map){
		if(map.containsKey(str)&&!isOriginalWord){  // 一个词只能由其他词组成，自己不能组成自己！  
			return map.get(str);
		}
		for(int i=1;i<str.length();i++){
			String left=str.substring(0,i);
			String right=str.substring(i);
			if(map.containsKey(left)&&map.get(left)==true&&canBuildWord(right,false,map)){
				return true;
			}
		}
		map.put(str,false);  // 记录str不能被其他的单词表示，如果以后再遇到str就可以不继续找了 
		return false;
	}

	public static String[] createGiantArray() {  
        String arr[] = {"test", "tester", "testertest", "testing", 
                "apple", "seattle", "banana",  "batting", "ngcat", 
                "batti","bat", "testingtester", "testbattingcat"};
        return arr;
    }
}

---EOF---