DrawSomething辅助（java版）(一)

最近你画我猜挺火的，于是就写了个辅助工具。

输入候选字符，以及单词长度，就可以匹配出所有符合的单词

使用Trie树改造了下，6W单词，虽然还有一个剪枝没有加，但是还是秒出，速度挺快的。

Trie树：

[java]
package org.huohua.drawsomething;

import java.util.*;

class TrieNode
{
TrieNode []m_child;
boolean m_end;
int m_maxdeep;

static Set s_Result = new HashSet();

TrieNode()
{
m_child = new TrieNode[26];
m_end = false;
m_maxdeep = 0;
}
int Insert(String word,int index)
{
if(index == word.length())
{
m_end =true;
return 0;
}
int sub = word.charAt(index)-'a';
if(m_child[sub] ==null)
{
m_child[sub] = new TrieNode();
}
int deep = m_child[sub].Insert(word, index+1);
if (deep+1 > m_maxdeep) m_maxdeep = deep+1;
return deep+1;
}

boolean Find(String word,int index)
{
if(index == word.length())
{
return m_end;
}
int sub = word.charAt(index)-'a';
if (sub>25 || sub<0)
return false;
if (m_child[sub] ==null)
return false;
return m_child[sub].Find(word, index+1);
}

boolean FindDrawSomething(String chars,int num,String cur)
{
if(m_maxdeep < num)
return false;
if (num==0)
{
if(m_end)
{
s_Result.add(cur);
return true;
}
return false;
}

boolean f = false;
for(int i=0; i {
int sub = chars.charAt(i)-'a';
if (sub>25 || sub<0)
continue;
if (m_child[sub] ==null)
continue;
String nextchars = chars.substring(0,i)+chars.substring(i+1);
boolean ret = m_child[sub].FindDrawSomething(nextchars,num-1,cur+chars.charAt(i));
if(ret)
f = true;
}
return f;
}
}

public class TrieTree
{
TrieNode m_root;
TrieTree()
{
m_root = new TrieNode();
}
void Insert(String word)
{
m_root.Insert(word,0);
}
void Build(ArrayList words)
{
m_root = new TrieNode();

for(String word :words)
{
Insert(word.toLowerCase());
}

}
boolean Find(String word)
{
return m_root.Find(word.toLowerCase(), 0);
}

boolean FindDrawSomething(String chars,int num)
{
if(chars.length() < num)
return false;
TrieNode.s_Result.clear();
return m_root.FindDrawSomething(chars.toLowerCase(), num,"");
}

}

Test
有个单词字典，是从别的软件下面找的，有6W单词

[java]
package org.huohua.drawsomething;


import java.io.*;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;


public class Test {
public static void main(String[] args) throws IOException {


BufferedReader br = new BufferedReader(new FileReader("E:\\HuohuaWorkspace\\java\\servlettest\\src\\org\\huohua\\drawsomething\\words3.dic"));
String word =null;
ArrayList words = new ArrayList();
while((word = br.readLine())!=null)
{
words.add(word);
}
System.out.println(words.size());