其实这事是源自解一道LeetCode 208. Implement Trie (Prefix Tree)。
题目本身并不难，就是构造一个多叉树。我第一次提交代码，AC了，但是效率不高，结果如下：
Runtime: 56 ms, faster than 11.64% of Java online submissions。
Memory Usage: 64.4 MB, less than 5.6% of Java online submissions for Implement Trie (Prefix Tree).
效率竟然这么低，那我得学习下各路大神的高效方案。但是看了几个，和我的方法并无区别，他们的效率肯定比较高的，不然不会把答案贴上来。那问题出在哪儿呢？我想了下，想起曾经遇到String的toCharArray和charAt方法效率似乎有差别，难道是这里的原因。
我第一次提交的代码（一部分）：
/** Inserts a word into the trie. */
public void insert(String word) {
Node node=head;
for(char c:word.toCharArray()){
if(node.next==null){
node.next=new Node[26];
}
Node tNode=node.next[c-'a'];
if(tNode==null){
tNode=new Node(c);
node.next[c-'a']=tNode;
}
node=tNode;
}
if(node!=null){
node.isLeaf=true;
}
}
然后我修改了遍历String字符那儿，变成了下面这样：
/** Inserts a word into the trie. */
public void insert(String word) {
Node node=head;
for(int i=0;i<word.length();i++){
char c=word.charAt(i);
if(node.next==null){
node.next=new Node[26];
}
Node tNode=node.next[c-'a'];
if(tNode==null){
tNode=new Node(c);
node.next[c-'a']=tNode;
}
node=tNode;
}
if(node!=null){
node.isLeaf=true;
}
}
一提交，差别可不小：
Runtime: 29 ms, faster than 99.37% of Java online submissions.
Memory Usage: 48.9 MB, less than 100.00% of Java online submissions.
然后去阅读了一下源码:
public char charAt(int index) {
if ((index < 0) || (index >= value.length)) {
throw new StringIndexOutOfBoundsException(index);
}
return value[index];
}
public char[] toCharArray() {
// Cannot use Arrays.copyOf because of class initialization order issues
char result[] = new char[value.length];
System.arraycopy(value, 0, result, 0, value.length);
return result;
}
其实看源码就很明显了，charAt本身内部也是数组操作，而toCharArray要copy一遍，既花时间又耗空间，如果只是读取功能，显然应该使用charAt。
