LeetCode 6: ZigZag Conversion ——Java中字符串拼接的效率问题

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P  A  H  NA P L S I I GY  I  R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

题目意思很简单，给定一个字符串以及行数之后输出一个按规定格式的的Z型字符串。本题我采用的方法思路很简单，算法复杂度也较好，是O(n),以下粘贴下我的代码：

public String convert(String s, int numRows) {    if(numRows<=1){      return s;    }    String result = "";    for(int i=0;i<numRows;i++){      int index = i;      int nums = 0;      while(index<s.length()){        if(i>0&&i<numRows-1){          result+=s.charAt(index);          if(nums%2==1){            index+=i*2;                  }          else{            index+=(numRows-1-i)*2;          }          nums++;        }        else{          result+=s.charAt(index);          index+=(numRows-1)*2;        }      }    }    return result;  }

但是一上LeetCode看了下击败的人数仅有10%,这就有点纳闷了，同样的算法复杂度却差距这么大，唯一有可能出现问题的地方就是字符串的拼接这时间开销太大了。

然后我将字符串的拼接方式进行更改：

StringBuilder result = new StringBuilder();result.append("123");

用该方法进行字符串拼接，以下是更改后的代码：

public String convert(String s, int numRows) {    if(numRows<=1){      return s;    }    StringBuilder result = new StringBuilder();    for(int i=0;i<numRows;i++){      int index = i;      int nums = 0;      while(index<s.length()){        if(i>0&&i<numRows-1){          result.append(s.charAt(index));          if(nums%2==1){            index+=i*2;                  }          else{            index+=(numRows-1-i)*2;          }          nums++;        }        else{          result.append(s.charAt(index));          index+=(numRows-1)*2;        }      }    }    return result.toString();  }

然后在LeetCode上跑了下，下面是结果的截图，击败了92.31%的用户，果然是字符串的拼接效率出现了问题。

下面介绍几种Java中字符串的拼接方法以及相应的时间复杂度：

1、最基础的String+=背后的实质其实是使用StringBuilder对象，究其本质是String对象不可变的原因。虽然编译器对其做了优化，使用StringBuilder的append方法进行追加，但是每循环一次都会创建一个StringBuilder对象，且都会调用toString方法转换成字符串，所以开销很大。因此执行一次字符串“+”,相当于 str = new StringBuilder(str).append("a").toString(); 所以该方法性能极其低下，不适用于大批量数据的拼接操作。

2、StringBuffer 和 StringBuilder 的append方法都继承自AbstractStringBuilder，整个逻辑都只做字符数组的加长，拷贝，到最后也不会创建新的String对象，所以速度很快，完成拼接处理后在程序中用strBuffer.toString()来得到最终的字符串。这两种方法适用于大批量字符串的拼接操作处理。

原标题：LeetCode 6: ZigZag Conversion ——Java中字符串拼接的效率问题

关键词：JAVA