电子商务网站建设与管理考试题/陕西网络营销优化公司

private int dif;//剩余不同次数private Node root;//根节点，没有值//内部节点类class Node{int num;//该节点对应字符串数量Node childs[];//以下标为26个字母,存储下一个节点boolean isLeaf;//是否为叶子节点public Node(){num=0;childs=new Node[26];isLeaf=false;}public boolean contains(char key){return childs[key-'a']!=null;}public Node get(char key){return childs[key-'a']==null?null:childs[key-'a'];}public void put(char key,Node n){childs[key-'a']=n;}public boolean isLeaf(){return isLeaf;}}//添加字符串public void put(String word){put(root,word);}private void put(Node root,String word){if(root==null)return;word=word.toLowerCase();char[] chs=word.toCharArray();int n=chs.length;Node cur=root;for (int i = 0; i < n; i++) {//如果不包含其中某个字符,创建新节点if(!cur.contains(chs[i])){cur.put(chs[i],new Node());}cur=cur.get(chs[i]);//如果包含则继续寻找下一个字符}cur.isLeaf=true;cur.num++;}//查询是否存在字符串public boolean contains(String word){return contains(root,word,0);}private boolean contains(Node root,String word,int idx){boolean find=false;if(idx==word.length()){//当到达结尾时，不同次数为1且包含该单词则为trueif(dif==0&&root.isLeaf()) return true;else return false;}char c=word.charAt(idx);for (int i = 0; i < 26; i++) {if(root.childs[i]==null) continue;//不包含某字符跳过else if(i==c-'a') //字符相同不减次数find|=contains(root.childs[i],word,idx+1);else if(dif==0) continue;//字符不同且次数为0跳过else{//进行回溯dif--;find|=contains(root.childs[i],word,idx+1);dif++;}}return find;//只要有一次则为true}public MagicDictionary() {root=new Node();}public void buildDict(String[] dictionary) {for(String s:dictionary){put(s);}}public boolean search(String searchWord) {dif=1;//每次重置次数return contains(searchWord);}