spellchecker.java

来自「PKU中一些数据结构基本算法题的java实现」· Java 代码 · 共 114 行

import java.util.*;


/**
 * ID:1035
 * @author yhm
 *
 */
public class Spellchecker {

	static SpellcheckerNode[][] array = new SpellcheckerNode[16][10000];
	static int[] size = new int[16];
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int sumOf = 0;
		int index = 0;
		while(sumOf!=2){
			String str = cin.next();
			if(str.equals("#")){
				sumOf++;
				continue;
			}
			if(sumOf==0){
				int len = str.length();
				array[len][size[len]] = new SpellcheckerNode(str,index);
				size[len]++;
				index++;
			}
			else{
				Find(str);
			}
		}

	}
	
	static void Find(String str){
		int len = str.length();
		List<SpellcheckerNode> list = new ArrayList<SpellcheckerNode>();
		
		
		for(int i=0;len<=15 && i<size[len];i++){
			String str1 = array[len][i].str;
			int sum=0;
			for(int j=0;j<len && sum<2;j++){
				if(str.charAt(j)!=str1.charAt(j)){
					sum++;
				}
			}
			if(sum==0){
				System.out.println(str+" is correct");
				return;
			}
			else if(sum==1){
				list.add(array[len][i]);
			}			
		}
		
		for(int i=0;len+1<=15 && i<size[len+1];i++){
			String str1 = array[len+1][i].str;
			int sum=0;
			for(int j=0,k=0;j<len && k<len+1 && sum<2;j++,k++){
				if(str.charAt(j)!=str1.charAt(k)){
					sum++;
					j--;
				}
			}
			if(sum==0 || sum==1){
				list.add(array[len+1][i]);
			}		
		}
		
		for(int i=0;len-1>=1 && i<size[len-1];i++){
			String str1 = array[len-1][i].str;
			int sum=0;
			for(int j=0,k=0;j<len && k<len-1 && sum<2;j++,k++){
				if(str.charAt(j)!=str1.charAt(k)){
					sum++;
					k--;
				}
			}
			if(sum==0 || sum==1){
				list.add(array[len-1][i]);
			}		
		}
		
		System.out.print(str+":");
		Collections.sort(list);
		Iterator<SpellcheckerNode> i = list.iterator();
		while(i.hasNext()){
			SpellcheckerNode n = i.next();
			System.out.print(" " + n.str);			
		}
		System.out.println();
	}

}


class SpellcheckerNode implements Comparable<SpellcheckerNode>{
	public int compareTo(SpellcheckerNode o) {
		// TODO Auto-generated method stub
		return index.compareTo(o.index);
	}
	String str;
	Integer index;
	public SpellcheckerNode(String str, int index) {
		super();
		this.str = str;
		this.index = index;
	}
}