leetcode 38. Count and Say

一个效率极其低下的版本：递归的写法，时间上慢？

public class Solution { public String countAndSay(int n) { if(n==1) return "1"; return count(countAndSay(n-1)); } public String count(String t){ String ans = ""; int len = t.length(); int cnt = 0; char pre = t.charAt(0); for(int i=0;i<len;i++){ if(i==len-1){ if(t.charAt(i)==pre){ cnt++; ans += cnt; ans += pre; }else{ ans += cnt; ans += pre; // before cnt = 1; pre = t.charAt(i); ans += cnt; ans += pre; // now } } else { if(t.charAt(i)==pre){ cnt++; }else{ ans += cnt; ans += pre; cnt = 1; pre = t.charAt(i); } } } return ans; } } 这是solution上非递归的写法，所以时间快？   还待深究。

public class Solution { public String countAndSay(int n) { StringBuilder curr=new StringBuilder("1"); StringBuilder prev; int count; char say; for (int i=1;i<n;i++){ prev=curr; curr=new StringBuilder(); count=1; say=prev.charAt(0); for (int j=1,len=prev.length();j<len;j++){ if (prev.charAt(j)!=say){ curr.append(count).append(say); count=1; say=prev.charAt(j); } else count++; } curr.append(count).append(say); } return curr.toString(); } }

嗯  原因不在于 递归还是迭代，而是  StringBuilder 与 String 的区别。