当前位置:首页 > 开发 > 编程语言 > Java > 正文

使用字典树和Hashtable两种方法解POJ 2503(JAVA)

发表于: 2012-11-24   作者:128kj   来源:转载   浏览:
摘要: poj2503题意:    给出一个最多有100000对单词的英语和外语的字典,然后给你一个外语单词 要求你查字典翻译成英语,如果词典里查不到就输出eh。 样例: Sample Input dog ogday cat atcay pig igpay froot ootfray loops oopslay atcay ittenkay oopslay
poj2503题意:
   给出一个最多有100000对单词的英语和外语的字典,然后给你一个外语单词 要求你查字典翻译成英语,如果词典里查不到就输出eh。
样例:

Sample Input

dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay

atcay
ittenkay
oopslay


Sample Output

cat
eh
loops


解法一:使用jdk中的Hashtable(或HashMap)
 import java.util.Scanner;
import java.util.Hashtable;

public class Main {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        Hashtable< String,String> table = new Hashtable< String, String>();
        String input;
        String [] array=new String[2];
        while(in.hasNext()){
            input=in.nextLine();
            if(input.length()==0)break;
            array=input.split(" ");
            table.put(array[1],array[0]);
        }
        while(in.hasNext()){
           input=in.nextLine();
         if(table.get(input)!=null) System.out.println(table.get(input));
         else System.out.println("eh");
        }
    }
}



方法二:使用字典树
思路:用所有的外语单词去建一棵字典树,然后向这棵字典树中查找给出的单词
import java.util.Scanner;
import java.text.DecimalFormat; 

class Trie{ //字典树
    Trie next[] = new Trie[26];//所有儿子节点
    String  enWord;// 用于记录对应的英语单词  
    public Trie(){
        enWord=null;
    }
} 
 
public class Main{ 
    Trie root = new Trie();
     
     void solve() {
        Scanner  in = new Scanner(System.in);
        String input;
        String [] array=new String[2];
        while(in.hasNext()){//用所有外文字符串,构造字典树
            input = in.nextLine();
            if(input.length()==0) break;
            array=input.split(" ");
            insert(array[1],array[0]);
        }
         while(in.hasNext()){
           input=in.nextLine();
           System.out.println(search(input));
        }
    }

    //建立字典树
    public void insert(String str,String enWord) {  //将一个外文字符串插入字典树
        if (str == null || str.length() == 0) {  
            return ;
        }  
        Trie node = root;  
        char[] letters=str.toCharArray();  
        for (int i = 0; i < str.length(); i++) {  
            int pos = letters[i] - 'a';  
            if (node.next[pos] == null) {  
                node.next[pos] = new Trie();  
                //node.son[pos].val = letters[i];  
            } 
            node = node.next[pos];  
        }  
       //外文字符串的最后一个节点,根节点到此节点构成了一个外文单词,此单词对应的英文单词为enWord;
        node.enWord = enWord;  
    }  

      
     // 在字典树中查找一个完全匹配的外文单词,返回其对应的英文单词.  
    public String search(String str) {  
        if (str == null || str.length() == 0) {  
            return null;  
        }  
        Trie node = root;  
        char[] letters=str.toCharArray();  
        for (int i = 0, len = str.length(); i < len; i++) {  
            int pos = letters[i] - 'a';  
            if (node.next[pos] != null) {  
                node = node.next[pos];  
            } else {  
                return "eh";  
            }  
        }  
        return node.enWord;  
    }  

    
    public static void main(String[] args) {
        Main test = new Main();
         test.solve();
    }
}



使用字典树和Hashtable两种方法解POJ 2503(JAVA)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
字典树 又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序
import java.util.Scanner; 方法一:时间复杂度O(n^3) class Edge { /** * 边的起点 */ char vexa;
首先,先上Hashtable.class中的代码,所有的Java实现方法都在这个文件中了。 Hashtable.class 当然
题目链接: hdu 1671 题目大意: 给出几串数组,是否存在一个串是另外一个串的前缀,是则输出"YES" 解
Stars Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 26354 Accepted: 11498 Descri
trie树——字典树 详细讲解!! 又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典
今天看了字典树原理,顺便AC了几个简单的题目,做一下总结。 (字典树) 字典树的基本功能是用来查
字典树是一种以树这种结构为基础建立的算法 ,那么字典树到底有哪些典型的应用呢? 1.字典树在串的
出处:http://www.cnblogs.com/pony1993/archive/2012/07/18/2596730.html(秦神的博客) 字典树(Tr
字典树,又称单词查找树,Trie树,是一种树形结构,典型应用是用于统计,排序和保存大量的字符串,
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号