数据结构之字符串

　　第一篇：数据结构之链表

　　第二篇：数据结构之栈和队列

　　第三篇：数据结构之二叉树

　　第四篇：数据结构之排序

　　在这篇文章里，我们关注和字符串相关的话题。

　　在谈论到字符串时，通常情况下，我们是在讨论ASCII码范围内的字符串，即它包括256个字符。在设计字符串相关的算法时，我们需要在时间和空间这两者之间进行权衡。

　　下面我们来看相关的题目。

判断字符串里出现的字符是否是唯一的。
思路：方案一：将字符串转换为字符数组，从第一个字符开始遍历，针对每个字符，判断字符串之前是否出现过该字符，如果出现过，说明该字符在字符串中不是唯一的。对应的空间复杂度O(1)，时间复杂度O(n*n)。

判断字符串中的字符是否唯一

 1 public static boolean Check(String value)
 2 {
 3     if (value == null || value.length() < 2) return true;
 4     char[] arrChars = value.toCharArray();
 5     for (int i = 1; i < arrChars.length; i++)
 6     {
 7         char ch = arrChars[i];
 8         for (int j = 0; j < i; j++)
 9         {
10             if (arrChars[j] == ch) return false;
11         }
12     }
13     
14     return true;
15 }

方案二：如果字符串中的字符都是ASCII码，那么可以建立一个长度为256的整型flag数组，数组的每个元素初始值是0，然后遍历字符串，将每个字符对应的ASCII码求出数组中对应位置的元素值，如果为0，说明字符串中暂时还没有出现该字符，将数组对应元素的值设置为1；如果为1，说明字符串中已经出现了该字符，有重复。

使用flag数组来判断字符串中字符是否唯一

 1 public static boolean Check2(String value)
 2 {
 3     if (value == null || value.length() < 2) return true;        
 4     char[] arrChars = value.toCharArray();
 5     int[] arrFlag = new int[256];
 6     for(int flag : arrFlag) flag = 0;
 7     for(char ch : arrChars)
 8     {
 9         if (arrFlag[(int)ch] == 1) return false;
10         arrFlag[(int)ch] = 1;
11     }
12     return true;
13 }

方案三：如果字符串空字符超出ASCII码，那么可以使用一个hashtable来模拟flag数组，将遍历过的每个字符以键的方式插入到hashtable中。代码略。

反转字符串
思路：循环替换（0-n/2），需要注意字符串的最后一位是否是'\0'。

反转字符串

 1 public static String reverse(String value)
 2 {
 3     if (value == null || value.length() < 3) return value;
 4     
 5     char[] arrChars = value.toCharArray();
 6     int length = value.length() - 1;
 7     for (int i = 0; i < length/2; i++)
 8     {
 9         char temp = arrChars[i];
10         arrChars[i] = arrChars[length - i];
11         arrChars[length - i] = temp;
12     }
13     arrChars[length] = '0';
14     return arrChars.toString();
15 }

删除字符串中的重复字符
思路：这个题目，同样有遍历和flag数组两种方式。首先来看遍历方式，时间复杂度是O(n*n)，空间复杂度是O(1)。

利用循环删除字符串中的重复字符

 1 public static void removeDuplicate2(String value)
 2 {
 3     if (value == null || value.length() < 2) return;
 4     char[] arrChars = value.toCharArray();
 5     int current = 0;
 6     for (int i = 1; i < arrChars.length; i++)
 7     {
 8         int j = 0;
 9         for (j = 0; j < i; j++)
10         {
11             if (arrChars[i] == arrChars[j]) break;
12         }
13         if (i == j) 
14         {
15             arrChars[current] = arrChars[i];
16             current++;
17         }
18     }
19     arrChars[current] = '0';
20     value = arrChars.toString();
21 }

接着是使用flag数组。

利用flag数组删除字符串中的重复字符

 1 public static void removeDuplicate3(String value)
 2 {
 3     if (value == null || value.length() < 2) return;
 4     int[] arrFlag = new int[256];
 5     for(int flag : arrFlag) flag = 0;
 6     char[] arrChars = value.toCharArray();
 7     int current = 0;
 8     for (int i = 0; i < arrChars.length; i++)
 9     {
10         if (arrFlag[(int)arrChars[i]] != 1)
11         {
12             arrChars[current] = arrChars[i];
13             arrFlag[(int)arrChars[i]] = 1;
14             current++;
15         }
16     }
17     arrChars[current] = '0';
18     value = arrChars.toString();
19 }

判断给定的两个字符串是否是变位词（包含的字符相同，但顺序不同）
思路：方案一：对两个字符串分别进行排序处理，然后比较排序后的两个字符串是否相同。代码略
方案二：采用flag数组，首先遍历第一个字符串，填充flag数组；然后遍历第二个字符串，同时检查flag数组。

利用flag数组判断两个字符串是否是变位词

 1 public static boolean isAnagram(String value1, String value2)
 2 {
 3     if (value1 == null || value2 == null || value1.length() != value2.length())
 4         return false;
 5     
 6     int[] arrFlag = new int[256];
 7     for(int flag : arrFlag) flag = 0;
 8     char[] arrChars1 = value1.toCharArray();
 9     for(char ch : arrChars1) arrFlag[ch]++;
10     char[] arrChars2 = value2.toCharArray();
11     for(char ch : arrChars2) 
12     {
13         if (arrChars1[ch] == 0)
14             return false;
15         arrChars1[ch]--;
16     }
17     return true;
18 }

将字符串中出现的所有空格替换为'%20'
思路：由于空格和'%20'长度不一致，这样替换后的字符串长度和原来的长度肯定不一样，对于这种情况，我们需要首先遍历一次字符串，计算出空格的数组，这样也就可以计算出新的字符串的长度，然后从后向前依次替换。

替换字符串中的空格为'%20'

 1 public static void replaceWhitespace(String value)
 2 {
 3     if (value == null)return;
 4     int count = 0;
 5     for(int i = 0; i < value.length(); i++)
 6     {
 7         if (value.charAt(i) == ' ')
 8         {
 9             count++;
10         }
11     }
12     if (count == 0) return;
13     int length = value.length() + 2 * count;
14     int current = length -1;
15     char[] arrChars = new char[length];
16     for (int i = value.length() - 1; i >= 0; i--)
17     {
18         if (value.charAt(i) == ' ')
19         {
20             arrChars[current] = '0';
21             arrChars[current - 1] = '2';
22             arrChars[current - 2] = '%';
23             current = current - 3;
24         }
25         else
26         {
27             arrChars[current] = value.charAt(i);
28             current--;
29         }
30     }
31     
32     value = arrChars.toString();
33 }

将N*N矩阵旋转90度
思路：我们可以拿3*3矩阵做例子，在旋转完毕后，前后矩阵元素的关系如下：
　　a[0][0]=>a[0][2]
　　a[0][1]=>a[1][2]
　　a[0][2]=>a[2][2]
　　a[1][0]=>a[0][1]
　　a[1][1]=>a[1][1]
　　a[1][2]=>a[2][1]
　　a[2][0]=>a[0][0]
　　a[2][1]=>a[1][0]
　　a[2][2]=>a[2][0]
我们可以得到以下转换规则：a[x][y]=>a[y][n-x]。

将矩阵旋转90度

 1 public static void rotate(int[][] matrix)
 2 {
 3     if (matrix == null) return;
 4     int length = matrix.length - 1;
 5     for (int i = 0; i < length/2; i++)
 6     {
 7         for (int j = 0; j < length; j++)
 8         {
 9             int temp = matrix[i][j];
10             matrix[i][j] = matrix[j][length - i];
11             matrix[j][length - i] = matrix[length - i][length - j];
12             matrix[length - i][length - j] = matrix[length - j][i];
13             matrix[length - j][i] = temp;
14         }
15     }
16 }

对N*M 矩阵进行处理，如果某个元素为0，则将该元素对应的行与列都设置为0
思路：不能直接对矩阵进行设置0的处理，因为再设置0后，还需要进行遍历，这样可能导致最终矩阵所有元素都为0，需要先将为0的元素进行保存，然后再处理。

对矩阵进行设0处理

 1 public static void setZeros(int[][] matrix)
 2 {
 3     if (matrix == null) return;
 4     int[] arrX = new int[matrix.length];
 5     int[] arrY = new int[matrix[0].length];
 6     for(int i = 0; i < matrix.length; i++)
 7     {
 8         for (int j = 0; j < matrix[i].length; j++)
 9         {
10             if (matrix[i][j] == 0)
11             {
12                 arrX[i] = 1;
13                 arrY[j] = 1;
14             }
15         }
16     }
17     for (int i = 0; i < matrix.length; i++)
18     {
19         for (int j = 0; j < matrix[i].length; j++)
20         {
21             if (arrX[i] == 1 || arrY[j] == 1)
22             {
23                 matrix[i][j] = 0;
24             }
25         }
26     }
27 }

判断一个字符串是否是另一个字符串经过翻转后得到的结果，例如cdab就是abcd进行翻转后的结果
思路：将一个字符串拼接到自己后面，然后判断另一个字符串是否是新字符串的子串。
判断两个字符串经过翻转后是否一致
```
1 public static boolean isRotation(String value1, String value2)
2 {
3     if (value1 == null || value2 == null || value1.length() != value2.length())
4         return false;
5     String newValue = value1 + value1;
6     return newValue.contains(value2);
7 }
```
最后，欢迎大家提出更多和字符串相关的面试题目，我们可以一起讨论。