极客时间算法课笔记整理13——理论讲解+面试题实战：字典树
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了极客时间算法课笔记整理13——理论讲解+面试题实战：字典树，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含15608字，纯文字阅读大概需要23分钟。
内容图文
这里写目录标题
字典树
存储结构：
java示例：256个ASCII码
python代码
面试题
208. Implement Trie (Prefix Tree)
我的方法：
class Trie {
private Trie[] links;
private final int R =26;
private boolean isEnd=false;
private boolean isSearch =false;
/** Initialize your data structure here. */
public Trie() {
links= new Trie[R];
}
/** Inserts a word into the trie. */
public void insert(String word) {
char[] target = word.toCharArray();
Trie[] cur =links;
Trie[] curT=cur;
int tmp=0;
for(char t : target){
tmp= t-'a';
if(cur[tmp]==null){cur[tmp]= new Trie();}//注意这句话，不判断cur[tmp]是否存在的话，新插入的apple会覆盖app
cur[tmp].isSearch=true;
curT=cur;
cur=cur[tmp].links;
}
curT[tmp].isSearch=true;
curT[tmp].isEnd=true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
char[] target = word.toCharArray();
Trie[] cur =links;
Trie[] curT=cur;
int tmp=0;
for(char t : target){
tmp= t-'a';
if(cur[tmp]==null || cur[tmp].isSearch==false){return false;}
curT=cur;
cur=cur[tmp].links;
}
if(curT[tmp].isEnd==true){return true;}
return false;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
char[] target = prefix.toCharArray();
Trie[] cur =links;
Trie[] curT=cur;
int tmp=0;
for(char t : target){
tmp= t-'a';
if(cur[tmp]==null || cur[tmp].isSearch==false){return false;}
curT=cur;
cur=cur[tmp].links;
}
if(curT[tmp].isSearch==true){return true;}
return false;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
最快的26s结果，启示：优先选择一个良好的数据结构进行存储，会获得比较好的结果：
class Trie {
class TrieNode {
char value;
TrieNode[] children;
boolean isWord;
public TrieNode(char value) {
this.value = value;
children = new TrieNode[26];
isWord = false;
}
public void insert(String word, int index) {
if (index == word.length()) {
isWord = true;
return;
}
char curr = word.charAt(index);
int position = curr - 'a';
if (children[position] == null) {
children[position] = new TrieNode(curr);
}
children[position].insert(word, index + 1);
}
public TrieNode find(String word, int index) {
if (index == word.length()) {
return this;
}
char curr = word.charAt(index);
int position = curr - 'a';
if (children[position] == null) {
return null;
}
return children[position].find(word, index + 1);
}
}
private TrieNode root;
/** Initialize your data structure here. */
public Trie() {
this.root = new TrieNode('r');
}
/** Inserts a word into the trie. */
public void insert(String word) {
root.insert(word, 0);
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode node = root.find(word, 0);
return node != null && node.isWord == true;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode node = root.find(prefix, 0);
return node != null;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
最少内存46200kb代码：
class Trie {
List<String> list;
/** Initialize your data structure here. */
public Trie() {
list = new ArrayList<String>();
}
/** Inserts a word into the trie. */
public void insert(String word) {
list.add(word);
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
return list.contains(word);
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
for (String s : list) {
if (s.startsWith(prefix)) {
return true;
}
}
return false;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
老师的python方法：
老师的数组JAVA方法：
212. Word Search II
老师的方法：
python代码：
java代码：13：22
我的方法：
public List<String> findWords(char[][] board, String[] words) {
Trie wordSet =new Trie();
List<String> res=new ArrayList<String>();
String curString;
for(int i=0;i<words.length;i++){
wordSet.insert(words[i]);
}
for(int i=0;i<board.length;i++){
for(int j=0;j<board[0].length;j++){
curString=String.valueOf(board[i][j]);
helper(board,wordSet,res,i,j,curString);
}
}
return res;
}
public void helper(char[][] board,Trie wordSet,List<String> res,int row,int col,String curString){
if(wordSet.search(curString)){res.add(new String(curString));}
else if(wordSet.startsWith(curString)){
if(row!=0){
StringBuilder stringBuilder=new StringBuilder(curString);
StringBuilder.append(String.valueOf(board[row-1][col]));//此处报错
helper(board,wordSet,res,row-1,col,curString);
}
if(row!=board.length-1){
StringBuilder stringBuilder=new StringBuilder(curString);
StringBuilder.append(String.valueOf(board[row+1][col]));
helper(board,wordSet,res,row+1,col,curString);
}
if(col!=0){
StringBuilder stringBuilder=new StringBuilder(curString);
StringBuilder.append(String.valueOf(board[row][col-1]));
helper(board,wordSet,res,row,col-1,curString);
}
if(col!=board[0].length-1){
StringBuilder stringBuilder=new StringBuilder(curString);
StringBuilder.append(String.valueOf(board[row][col+1]));
helper(board,wordSet,res,row,col+1,curString);
}
}
}
class Trie {
private Trie[] links;
private final int R =26;
private boolean isEnd=false;
private boolean isSearch =false;
/** Initialize your data structure here. */
public Trie() {
links= new Trie[R];
}
/** Inserts a word into the trie. */
public void insert(String word) {
char[] target = word.toCharArray();
Trie[] cur =links;
Trie[] curT=cur;
int tmp=0;
for(char t : target){
tmp= t-'a';
if(cur[tmp]==null){cur[tmp]= new Trie();}//注意这句话，不判断cur[tmp]是否存在的话，新插入的apple会覆盖app
cur[tmp].isSearch=true;
curT=cur;
cur=cur[tmp].links;
}
curT[tmp].isSearch=true;
curT[tmp].isEnd=true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
char[] target = word.toCharArray();
Trie[] cur =links;
Trie[] curT=cur;
int tmp=0;
for(char t : target){
tmp= t-'a';
if(cur[tmp]==null || cur[tmp].isSearch==false){return false;}
curT=cur;
cur=cur[tmp].links;
}
if(curT[tmp].isEnd==true){return true;}
return false;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
char[] target = prefix.toCharArray();
Trie[] cur =links;
Trie[] curT=cur;
int tmp=0;
for(char t : target){
tmp= t-'a';
if(cur[tmp]==null || cur[tmp].isSearch==false){return false;}
curT=cur;
cur=cur[tmp].links;
}
if(curT[tmp].isSearch==true){return true;}
return false;
}
}
更改后
class Solution {
public List<String> findWords(char[][] board, String[] words) {
Trie wordSet =new Trie();
List<String> res=new ArrayList<String>();
String curString;
for(int i=0;i<words.length;i++){
wordSet.insert(words[i]);
}
for(int i=0;i<board.length;i++){
for(int j=0;j<board[0].length;j++){
curString=String.valueOf(board[i][j]);
helper(board,wordSet,res,i,j,curString);
}
}
return res;
}
public void helper(char[][] board,Trie wordSet,List<String> res,int row,int col,String curString){
if(wordSet.search(curString)){res.add(new String(curString));}
else if(wordSet.startsWith(curString)){
if(row!=0){
char[] tmp=curString.toCharArray();
int l=tmp.length;
char[] ntmp=new char[l+1];
for(int i =0;i<l;i++){
ntmp[i]=tmp[i];
}
ntmp[l]=board[row-1][col];
curString=String.valueOf(ntmp);
helper(board,wordSet,res,row-1,col,curString);
}
if(row!=board.length-1){
char[] tmp=curString.toCharArray();
int l=tmp.length;
char[] ntmp=new char[l+1];
for(int i =0;i<l;i++){
ntmp[i]=tmp[i];
}
ntmp[l]=board[row+1][col];
curString=String.valueOf(ntmp);
helper(board,wordSet,res,row+1,col,curString);
}
if(col!=0){
char[] tmp=curString.toCharArray();
int l=tmp.length;
char[] ntmp=new char[l+1];
for(int i =0;i<l;i++){
ntmp[i]=tmp[i];
}
ntmp[l]=board[row][col-1];
curString=String.valueOf(ntmp);
helper(board,wordSet,res,row,col-1,curString);
}
if(col!=board[0].length-1){
char[] tmp=curString.toCharArray();
int l=tmp.length;
char[] ntmp=new char[l+1];
for(int i =0;i<l;i++){
ntmp[i]=tmp[i];
}
ntmp[l]=board[row][col+1];
curString=String.valueOf(ntmp);
helper(board,wordSet,res,row,col+1,curString);
}
}
}
class Trie {
private Trie[] links;
private final int R =26;
private boolean isEnd=false;
private boolean isSearch =false;
/** Initialize your data structure here. */
public Trie() {
links= new Trie[R];
}
/** Inserts a word into the trie. */
public void insert(String word) {
char[] target = word.toCharArray();
Trie[] cur =links;
Trie[] curT=cur;
int tmp=0;
for(char t : target){
tmp= t-'a';
if(cur[tmp]==null){cur[tmp]= new Trie();}//注意这句话，不判断cur[tmp]是否存在的话，新插入的apple会覆盖app
cur[tmp].isSearch=true;
curT=cur;
cur=cur[tmp].links;
}
curT[tmp].isSearch=true;
curT[tmp].isEnd=true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
char[] target = word.toCharArray();
Trie[] cur =links;
Trie[] curT=cur;
int tmp=0;
for(char t : target){
tmp= t-'a';
if(cur[tmp]==null || cur[tmp].isSearch==false){return false;}
curT=cur;
cur=cur[tmp].links;
}
if(curT[tmp].isEnd==true){return true;}
return false;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
char[] target = prefix.toCharArray();
Trie[] cur =links;
Trie[] curT=cur;
int tmp=0;
for(char t : target){
tmp= t-'a';
if(cur[tmp]==null || cur[tmp].isSearch==false){return false;}
curT=cur;
cur=cur[tmp].links;
}
if(curT[tmp].isSearch==true){return true;}
return false;
}
}
}
class Solution {
public List<String> findWords(char[][] board, String[] words) {
Trie wordSet =new Trie();
List<String> res=new ArrayList<String>();
int[][] count =new int[board.length][board[0].length];
String curString;
for(int i=0;i<words.length;i++){
wordSet.insert(words[i]);
}
for(int i=0;i<board.length;i++){
for(int j=0;j<board[0].length;j++){
curString=String.valueOf(board[i][j]);
helper(board,wordSet,res,i,j,curString,count);
}
}
return res;
}
public void helper(char[][] board,Trie wordSet,List<String> res,int row,int col,String curString,int[][] count){
if(wordSet.search(curString)){
res.add(new String(curString));
wordSet.delete(new String(curString));
}
if(wordSet.startsWith(curString)){
count[row][col]=1;
char[] tmp=curString.toCharArray();
int l=tmp.length;
char[] ntmp=new char[l+1];
for(int i =0;i<l;i++){
ntmp[i]=tmp[i];
}
if(row!=0 && count[row-1][col]!=1){
ntmp[l]=board[row-1][col];
curString=String.valueOf(ntmp);
helper(board,wordSet,res,row-1,col,curString,count);
}
if(row!=board.length-1 && count[row+1][col]!=1){
ntmp[l]=board[row+1][col];
curString=String.valueOf(ntmp);
helper(board,wordSet,res,row+1,col,curString,count);
}
if(col!=0 && count[row][col-1]!=1){
ntmp[l]=board[row][col-1];
curString=String.valueOf(ntmp);
helper(board,wordSet,res,row,col-1,curString,count);
}
if(col!=board[0].length-1 && count[row][col+1]!=1){
ntmp[l]=board[row][col+1];
curString=String.valueOf(ntmp);
helper(board,wordSet,res,row,col+1,curString,count);
}
count[row][col]=0;
}
}
class Trie {
private Trie[] links;
private final int R =26;
private boolean isEnd=false;
private boolean isSearch =false;
/** Initialize your data structure here. */
public Trie() {
links= new Trie[R];
}
/** Inserts a word into the trie. */
public void insert(String word) {
char[] target = word.toCharArray();
Trie[] cur =links;
Trie[] curT=cur;
int tmp=0;
for(char t : target){
tmp= t-'a';
if(cur[tmp]==null){cur[tmp]= new Trie();}//注意这句话，不判断cur[tmp]是否存在的话，新插入的apple会覆盖app
cur[tmp].isSearch=true;
curT=cur;
cur=cur[tmp].links;
}
curT[tmp].isSearch=true;
curT[tmp].isEnd=true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
char[] target = word.toCharArray();
Trie[] cur =links;
Trie[] curT=cur;
int tmp=0;
for(char t : target){
tmp= t-'a';
if(cur[tmp]==null || cur[tmp].isSearch==false){return false;}
curT=cur;
cur=cur[tmp].links;
}
if(curT[tmp].isEnd==true){return true;}
return false;
}
public boolean delete(String word) {
char[] target = word.toCharArray();
Trie[] cur =links;
Trie[] curT=cur;
int tmp=0;
for(char t : target){
tmp= t-'a';
if(cur[tmp]==null || cur[tmp].isSearch==false){return false;}
curT=cur;
cur=cur[tmp].links;
}
curT[tmp].isEnd=false;
return true;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
char[] target = prefix.toCharArray();
Trie[] cur =links;
Trie[] curT=cur;
int tmp=0;
for(char t : target){
tmp= t-'a';
if(cur[tmp]==null || cur[tmp].isSearch==false){return false;}
curT=cur;
cur=cur[tmp].links;
}
if(curT[tmp].isSearch==true){return true;}
return false;
}
}
}
输入：
[["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
["oath","pea","eat","rain","oathi","oathk","oathf","oate","oathii","oathfi","oathfii"]
[["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
["oath","pea","eat","rain"]
[["a","a"]]
["a"]
[["a","a"]]
["aaa"]
[["a","a"],["a","a"]]
["aaaaa"]
输出：
["oath","oathk","oathf","oathfi","oathfii","oathi","oathii","oate","eat"]
["oath","eat"]
["a"]
[]
[]
Java——在指定位置拼接和插入字符串
命中的缘分 2018-10-15 16:30:54 47251 收藏 19
分类专栏： Java EE Java基础 文章标签： Java 字符串
版权
在指定位置拼接和插入字符串
在日常开发中我们经常会碰到对字符串的操作，今天就来总结下Java中对字符串的拼接。
拼接字符串可分为两种：
1.在字符串末尾添加字符串；
2.在字符串任意位置添加字符串；
1.在字符串末尾添加字符串
我们可以用StringBuilder（效率高，线程不安全）和StringBuffer（效率低，线程安全）的append()方法。
例：
StringBuilder stringBuilder=new StringBuilder("1234ac");
stringBuilder.append("123");
最后的结果：
1234ac123
append（）方法是往字符串后面追加字符串；
2.在任意位置添加字符串
1.官方给我们提供了insert（）方法，该方法是在索引的前面添加字符串
例：
StringBuffer stringBuilder1=new StringBuffer("20180918");
stringBuilder1.insert(6,"-");
stringBuilder1.insert(4,"-");
最后结果：
2018-09-18
2.假如字符串比较长，我们不太好知道他的索引，可以通过方法indexOf（）来获取他的索引
如：int index=stringBuilder2.indexOf(“abc”);
这个就会返回第一个匹配到字符串的第一个字母的索引，这里返回的索引为4；
然后再通过insert方法去添加字符串
StringBuilder stringBuilder2=new StringBuilder("1234abcdabc12");
int index=stringBuilder2.indexOf("abc");
stringBuilder2.insert(index,"131");
最后结果
1234131abcdabc12
通过indexOf()方法和insert（）方法的配合使用我们就可以在任意位置添加字符串了。
Java中char和String的转换
耀凯考前突击大师 2016-08-01 09:08:57 119812 收藏 35
分类专栏： Java 文章标签： java string
版权
Java中char是一个基本类型，而String是一个引用类型。有时候我们需要在它们之间互相转换。
String转换为char
在Java中将String转换为char是非常简单的。
1. 使用String.charAt(index)（返回值为char）可以得到String中某一指定位置的char。
2. 使用String.toCharArray()（返回值为char[]）可以得到将包含整个String的char数组。这样我们就能够使用从0开始的位置索引来访问string中的任意位置的元素。
char转换为String
将char转换为String大致有6种方法。总结如下：
1. String s = String.valueOf('c'); //效率最高的方法
2. String s = String.valueOf(new char[]{'c'}); //将一个char数组转换成String
3. String s = Character.toString('c');
// Character.toString(char)方法实际上直接返回String.valueOf(char)
4. String s = new Character('c').toString();
5. String s = "" + 'c';
// 虽然这个方法很简单，但这是效率最低的方法
// Java中的String Object的值实际上是不可变的，是一个final的变量。
// 所以我们每次对String做出任何改变，都是初始化了一个全新的String Object并将原来的变量指向了这个新String。
// 而Java对使用+运算符处理String相加进行了方法重载。
// 字符串直接相加连接实际上调用了如下方法：
// new StringBuilder().append("").append('c').toString();
6. String s = new String(new char[]{'c'});
内容总结
以上是互联网集市为您收集整理的极客时间算法课笔记整理13——理论讲解+面试题实战：字典树全部内容，希望文章能够帮你解决极客时间算法课笔记整理13——理论讲解+面试题实战：字典树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】