JAVA程序设计：前缀和后缀搜索（LeetCode：745）

给定多个 words，words[i] 的权重为 i 。

设计一个类 WordFilter 实现函数WordFilter.f(String prefix, String suffix)。这个函数将返回具有前缀 prefix 和后缀suffix 的词的最大权重。如果没有这样的词，返回 -1。

例子:

输入:
WordFilter(["apple"])
WordFilter.f("a", "e") // 返回 0
WordFilter.f("b", "") // 返回 -1
注意:

words的长度在[1, 15000]之间。
对于每个测试用例，最多会有words.length次对WordFilter.f的调用。
words[i]的长度在[1, 10]之间。
prefix, suffix的长度在[0, 10]之前。
words[i]和prefix, suffix只包含小写字母。

方法一：暴力匹配每个单词的前后缀（超时）

class WordFilter {
	
	String[] words;

    public WordFilter(String[] words) {
    	this.words=words;
    }
    
    public int f(String prefix, String suffix) {
    	for(int i=words.length-1;i>=0;i--)
    		if(words[i].startsWith(prefix) && words[i].endsWith(suffix))
    			return i;
    	return -1;
    }
}

方法二：将前后缀合并为一个单词，加入字典树方便后续查找，其中两个单词合并为一个单词的方法有很多种。例如我们可以交叉合并，假如prefix="app",suffix="see",则合并后可以为“aepeps”,若要查询的前后缀不等长的话可以将少的部分变为none。当然我们也可以通过其他方法进行合并，方法不止一种。

class WordFilter {
	
	class Tree{
		
		int val;
		Map<Integer,Tree> children; 
		
		public Tree() {
			val=0;
			children=new HashMap<>();
		}
	}
	
	Tree root;

    public WordFilter(String[] words) {
    	
    	int weight=0;
    	root=new Tree();
    	
    	for(String word : words) {
    		Tree cur=root;
    		cur.val=weight;
    		int len=word.length();
    		char[] chars=word.toCharArray();
    		for(int i=0;i<len;i++) {
    			Tree tmp=cur;
    			for(int j=i;j<len;j++) {
    				int code=(chars[j]-'`')*27;
    				if(tmp.children.get(code)==null)
    					tmp.children.put(code, new Tree());
    				tmp=tmp.children.get(code);
    				tmp.val=weight;
    			}
    			tmp=cur;
    			for(int k=len-1-i;k>=0;k--) {
    				int code=chars[k]-'`';
    				if(tmp.children.get(code)==null)
    					tmp.children.put(code, new Tree());
    				tmp=tmp.children.get(code);
    				tmp.val=weight;
    			}
    			int code=(chars[i]-'`')*27+(chars[len-1-i]-'`');
    			if(cur.children.get(code)==null)
    				cur.children.put(code, new Tree());
    			cur=cur.children.get(code);
    			cur.val=weight;
    		}
    		weight++;
    	}
    }
    
    public int f(String prefix, String suffix) {
    	Tree cur=root;
    	int i=0,j=suffix.length()-1;
    	while(i<prefix.length() || j>=0) {
    		char c1=i<prefix.length()?prefix.charAt(i):'`';
    		char c2=j>=0?suffix.charAt(j):'`';
    		int code=(c1-'`')*27+(c2-'`');
    		cur=cur.children.get(code);
    		if(cur==null) return -1;
    		i++; j--;
    	}
    	return cur.val;
    }
}