T38 外观数列

思想：迭代枚举即可(当然也可以递归求)，这里利用Map来存储之前的结果，也可以用数组也就是dp来实现 时间复杂度O(n*m) m是生成子串的最大长度 ，空间复杂度O(n)

class Solution { public String countAndSay(int n) { if(n==1){ return "1"; } if(n==2){ return "11"; } Map<Integer,String> map = new HashMap<>(); map.put(1,"1"); map.put(2,"11"); for(int k=3;k<=n;k++){ String preStr = map.get(k-1); int start = 0; StringBuilder temp = new StringBuilder(); while(start<preStr.length()){ int end = start; while(end<preStr.length()&&preStr.charAt(end)==preStr.charAt(start)){ end++; } temp.append(end-start); temp.append(preStr.charAt(start)); start = end; } map.put(k,temp.toString()); } return map.get(n); } }

当然也可以采用数组实现

class Solution { public String countAndSay(int n) { if(n==1){ return "1"; } if(n==2){ return "11"; } String[]dp = new String[n+1]; dp[1] = "1"; dp[2] = "11"; for(int k=3;k<=n;k++){ String preStr = dp[k-1]; int start = 0; StringBuilder temp = new StringBuilder(); while(start<preStr.length()){ int end = start; while(end<preStr.length()&&preStr.charAt(end)==preStr.charAt(start)){ end++; } temp.append(end-start); temp.append(preStr.charAt(start)); start = end; } dp[k] = temp.toString(); } return dp[n]; } }

case3:递归实现 时间复杂度O(n*m) 空间复杂度O(n)

class Solution { public String countAndSay(int n) { if(n==1){ return "1"; } if(n==2){ return "11"; } String preStr = countAndSay(n-1); int start = 0; StringBuilder temp = new StringBuilder(); while(start<preStr.length()){ int end = start; while(end<preStr.length()&&preStr.charAt(end)==preStr.charAt(start)){ end++; } temp.append(end-start); temp.append(preStr.charAt(start)); start = end; } return temp.toString(); } }