其實(shí)這事是源自解一道LeetCode 208. Implement Trie (Prefix Tree)。
題目本身并不難，就是構(gòu)造一個(gè)多叉樹。我第一次提交代碼，AC了，但是效率不高，結(jié)果如下：
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).
效率竟然這么低，那我得學(xué)習(xí)下各路大神的高效方案。但是看了幾個(gè)，和我的方法并無區(qū)別，他們的效率肯定比較高的，不然不會(huì)把答案貼上來。那問題出在哪兒呢？我想了下，想起曾經(jīng)遇到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;
}
其實(shí)看源碼就很明顯了，charAt本身內(nèi)部也是數(shù)組操作，而toCharArray要copy一遍，既花時(shí)間又耗空間，如果只是讀取功能，顯然應(yīng)該使用charAt。
