題意：字處理程序檢查輸入的單詞是否正確。若不正確，則按照規則在字典中找與該單詞相近的單詞。
解題思路：按照題目給出的規則模擬。
要點：要注意查找效率，遍歷會超時。此處用的是TreeMap，查找效率log2(N)。
代碼
1
import java.io.*;
2import java.util.*;
3class Main
4
{
5
private static TreeMap<String, Integer> dic = new TreeMap<String, Integer>();
6 private static TreeSet<MyNode> nodes = new TreeSet<MyNode>();
7
private static char[] alp = {
8 'a', 'b', 'c', 'd', 'e', 'f', 'g',
9 'h', 'i', 'j', 'k', 'l', 'm', 'n',
10 'o', 'p', 'q', 'r', 's', 't',
11 'u', 'v', 'w', 'x', 'y', 'z',
12
};
13 public static void main(String[] args)
14 {
15
16 Scanner sc = new Scanner(System.in);
17 String strt = sc.nextLine();
18 int count = 0;
19 while(!"#".equals(strt))
20 {
21 dic.put(strt, count++);
22 strt = sc.nextLine();
23 }
24 strt = sc.nextLine();
25 while(!"#".equals(strt))
26 {
27 if(dic.get(strt) != null)
28 {
29 System.out.println(strt + " is correct");
30
31 }
32 else{
33 nodes.clear();
34 rule1(strt);
35 rule2(strt);
36 rule3(strt);
37 System.out.print(strt + ":");
38
39 Iterator<MyNode> it = nodes.iterator();
40 while(it.hasNext())
41 {
42 MyNode nd = it.next();
43 System.out.print(" " + nd.getStr());
44
45 }
46 System.out.println();
47
48
49 }
50
51 strt = sc.nextLine();
52 }
53 }
54 private static void rule1(String strt)
55 {
56
57 char[] charArry = strt.toCharArray();
58 for(int i = 0; i < charArry.length; i++)
59 {
60 String str2 = new String(charArry, 0, i) +
61 new String(charArry, i + 1, charArry.length - i - 1);
62
63 Integer p = dic.get(str2);
64 if(p != null)
65 {
66 nodes.add(new MyNode(str2, p));
67 }
68 else if(strt.length() == 1)
69 {
70 for(int j = 0; j < alp.length; j++)
71 {
72 p = dic.get("" + alp[j]);
73 if(p != null)
74 nodes.add(new MyNode("" + alp[j], p));
75 }
76 }
77
78 }
79 }
80
81 private static final void rule2(String strt)
82 {
83 char[] charArry = strt.toCharArray();
84 for(int i = 0; i < charArry.length; i++)
85 {
86 for(int j = 0; j < alp.length; j++)
87 {
88 char c = charArry[i];
89 charArry[i] = alp[j];
90 String str2 = new String(charArry);
91 Integer p = dic.get(str2);
92 if(p != null)
93 {
94 nodes.add(new MyNode(str2, p));
95 }
96
97 charArry[i] = c;
98 }
99 }
100 }
101
102 private static void rule3(String strt)
103 {
104 StringBuffer buf = new StringBuffer();
105 char[] charArry = strt.toCharArray();
106 for(int i = 0; i <= charArry.length; i++)
107 {
108 for(int j = 0; j < alp.length; j++)
109 {
110
111 String str2 = new String(charArry, 0, i) + alp[j]
112 + new String(charArry, i, charArry.length - i);
113 Integer p = dic.get(str2);
114 if(p != null)
115 {
116 nodes.add(new MyNode(str2, p));
117 }
118 }
119 }
120 }
121
}
122
123/**//*
124*/
125class MyNode implements Comparable<MyNode>
126{
127 private String str;
128 private int p;
129 MyNode(String str, int p)
130 {
131 this.str = str;
132 this.p = p;
133 }
134 public String getStr()
135 {
136 return str;
137 }
138 public int compareTo(MyNode n2){
139 return this.p - n2.p;
140 }
141}
142
143 posted on 2013-04-09 15:17
小鼠標 閱讀(160)
評論(0) 編輯 收藏 引用 所屬分類:
Java基礎練習