这里写目录标题
字典树
存储结构：
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'});