我正在尝试实现一个程序，该程序将接受用户输入，将该字符串拆分为标记，然后在字典中搜索该字符串中的单词。我对解析字符串的目标是让每个标记都是英语单词。
例如：
Input:
aman
Split Method:
a man
a m an
a m a n
am an
am a n
ama n
Desired Output:
a man
我目前有这段代码，它可以完成所有操作，直到所需的输出部分：
import java.util.Scanner;
import java.io.*;
public class Words {
public static String[] dic = new String[80368];
public static void split(String head, String in) {
// head + " " + in is a segmentation
String segment = head + " " + in;
// count number of dictionary words
int count = 0;
Scanner phraseScan = new Scanner(segment);
while (phraseScan.hasNext()) {
String word = phraseScan.next();
for (int i=0; i<dic.length; i++) {
if (word.equalsIgnoreCase(dic[i])) count++;
}
}
System.out.println(segment + "\t" + count + " English words");
// recursive calls
for (int i=1; i<in.length(); i++) {
split(head+" "+in.substring(0,i), in.substring(i,in.length()));
}
}
public static void main (String[] args) throws IOException {
Scanner scan = new Scanner(System.in);
System.out.print("Enter a string: ");
String input = scan.next();
System.out.println();
Scanner filescan = new Scanner(new File("src:\\dictionary.txt"));
int wc = 0;
while (filescan.hasNext()) {
dic[wc] = filescan.nextLine();
wc++;
}
System.out.println(wc + " words stored");
split("", input);
}
}
我知道有更好的方法来存储字典（例如二叉搜索树或哈希表），但我不知道如何实现这些。
我不知道如何实现一种方法来检查分割字符串以查看每个片段是否都是字典中的单词。
任何帮助都会很棒， 谢谢你
如果您想支持 20 个或更多字符，则以各种可能的方式分割输入字符串不会在合理的时间内完成。这是一种更有效的方法，内嵌评论：
public static void main(String[] args) throws IOException {
// load the dictionary into a set for fast lookups
Set<String> dictionary = new HashSet<String>();
Scanner filescan = new Scanner(new File("dictionary.txt"));
while (filescan.hasNext()) {
dictionary.add(filescan.nextLine().toLowerCase());
}
// scan for input
Scanner scan = new Scanner(System.in);
System.out.print("Enter a string: ");
String input = scan.next().toLowerCase();
System.out.println();
// place to store list of results, each result is a list of strings
List<List<String>> results = new ArrayList<>();
long time = System.currentTimeMillis();
// start the search, pass empty stack to represent words found so far
search(input, dictionary, new Stack<String>(), results);
time = System.currentTimeMillis() - time;
// list the results found
for (List<String> result : results) {
for (String word : result) {
System.out.print(word + " ");
}
System.out.println("(" + result.size() + " words)");
}
System.out.println();
System.out.println("Took " + time + "ms");
}
public static void search(String input, Set<String> dictionary,
Stack<String> words, List<List<String>> results) {
for (int i = 0; i < input.length(); i++) {
// take the first i characters of the input and see if it is a word
String substring = input.substring(0, i + 1);
if (dictionary.contains(substring)) {
// the beginning of the input matches a word, store on stack
words.push(substring);
if (i == input.length() - 1) {
// there's no input left, copy the words stack to results
results.add(new ArrayList<String>(words));
} else {
// there's more input left, search the remaining part
search(input.substring(i + 1), dictionary, words, results);
}
// pop the matched word back off so we can move onto the next i
words.pop();
}
}
}
输出示例：
Enter a string: aman
a man (2 words)
am an (2 words)
Took 0ms
这里有一个更长的输入：
Enter a string: thequickbrownfoxjumpedoverthelazydog
the quick brown fox jump ed over the lazy dog (10 words)
the quick brown fox jump ed overt he lazy dog (10 words)
the quick brown fox jumped over the lazy dog (9 words)
the quick brown fox jumped overt he lazy dog (9 words)
Took 1ms
如果我的答案看起来很愚蠢，那是因为你真的很接近，而我不确定你被困在哪里。
上面给出的代码最简单的方法是简单地添加一个单词数计数器，并将其与匹配的单词数进行比较
int count = 0; int total = 0;
Scanner phraseScan = new Scanner(segment);
while (phraseScan.hasNext()) {
total++
String word = phraseScan.next();
for (int i=0; i<dic.length; i++) {
if (word.equalsIgnoreCase(dic[i])) count++;
}
}
if(total==count) System.out.println(segment);
将其实现为哈希表可能会更好（当然更快），而且非常容易。
HashSet<String> dict = new HashSet<String>()
dict.add("foo")// add your data
int count = 0; int total = 0;
Scanner phraseScan = new Scanner(segment);
while (phraseScan.hasNext()) {
total++
String word = phraseScan.next();
if(dict.contains(word)) count++;
}
还有其他更好的方法可以做到这一点。一种是 trie (http://en.wikipedia.org/wiki/Trie)，它的查找速度稍慢，但存储数据的效率更高。如果您有一个很大的字典，您可能无法将其放入内存中，因此您可以使用数据库或键值存储，例如 BDB (http://en.wikipedia.org/wiki/Berkeley_DB)
package LinkedList;
import java.util.LinkedHashSet;
public class dictionaryCheck {
private static LinkedHashSet<String> set;
private static int start = 0;
private static boolean flag;
public boolean checkDictionary(String str, int length) {
if (start >= length) {
return flag;
} else {
flag = false;
for (String word : set) {
int wordLen = word.length();
if (start + wordLen <= length) {
if (word.equals(str.substring(start, wordLen + start))) {
start = wordLen + start;
flag = true;
checkDictionary(str, length);
}
}
}
}
return flag;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
set = new LinkedHashSet<String>();
set.add("Jose");
set.add("Nithin");
set.add("Joy");
set.add("Justine");
set.add("Jomin");
set.add("Thomas");
String str = "JoyJustine";
int length = str.length();
boolean c;
dictionaryCheck obj = new dictionaryCheck();
c = obj.checkDictionary(str, length);
if (c) {
System.out
.println("String can be found out from those words in the Dictionary");
} else {
System.out.println("Not Possible");
}
}
}