字符串算法
- 字符串字符判重算法
- 字符串反转算法
- 字符串左旋算法
- 字符串右旋算法
- 字符串旋转匹配算法
- 字符串包含算法
- 字符串删除算法
- 字符串原地替换算法
- 字符串压缩算法
- 字符串变位词检测算法
- 字符串转整数算法
- 字符串全排列算法
- 字符串字典序组合算法
- 字符串的（括号）生成算法
字符串字符判重算法
给定字符串，确定是否字符串中的所有字符全都是不同的。假设字符集是 ASCII。
1 using System; 2 using System.Collections.Generic; 3 4 namespace AlgorithmTesting 5 { 6 class Program 7 { 8 static void Main(string[] args) 9 { 10 Console.WriteLine(IsUniqueChars("asdf5678888888".ToCharArray())); 11 Console.WriteLine(IsUniqueChars("asdf5678!@#$%^&".ToCharArray())); 12 Console.WriteLine(IsUniqueSmallAlphabetChars("asdf5678!@#$%^&".ToCharArray())); 13 Console.WriteLine(IsUniqueSmallAlphabetChars("asdf5678".ToCharArray())); 14 Console.WriteLine(IsUniqueSmallAlphabetChars("asdf{}".ToCharArray())); 15 Console.WriteLine(IsUniqueSmallAlphabetChars("asdf".ToCharArray())); 16 Console.ReadKey(); 17 } 18 19 static bool IsUniqueChars(char[] str) 20 { 21 if (str.Length > 256) 22 return false; 23 24 // 为每个字符保存一个是否存在标记 25 bool[] charSet = new bool[256]; 26 for (int i = 0; i < str.Length; i++) 27 { 28 var index = (byte)str[i]; 29 if (charSet[index]) 30 { 31 return false; 32 } 33 charSet[index] = true; 34 } 35 36 return true; 37 } 38 39 static bool IsUniqueSmallAlphabetChars(char[] str) 40 { 41 if (str.Length > 26) 42 return false; 43 44 // 使用位操作以改进空间占用 45 int checker = 0; 46 for (int i = 0; i < str.Length; i++) 47 { 48 int index = str[i] - 'a'; 49 if (index < 0 50 || index > 26 51 || (checker & (1 << index)) > 0) 52 { 53 return false; 54 } 55 checker |= (1 << index); 56 } 57 58 return true; 59 } 60 } 61 }
字符串反转算法
有字符串 s1 = "ABC1DEF"，要求将其反转成 "FED1CBA"。
1 using System; 2 3 namespace ConsoleApplication1 4 { 5 class Program 6 { 7 static void Main(string[] args) 8 { 9 string text1 = "ABC1DEF"; 10 string text2 = "ABC1DEFG"; 11 char[] t1 = text1.ToCharArray(); 12 char[] t2 = text2.ToCharArray(); 13 14 ReversePartOfString(t1, 1, t1.Length - 2); 15 ReversePartOfString(t2, 1, t2.Length - 2); 16 17 string s1 = new string(t1); 18 string s2 = new string(t2); 19 Console.WriteLine(s1); 20 Console.WriteLine(s2); 21 22 string text3 = "ABC1DEF"; 23 string text4 = "ABC1DEFG"; 24 char[] t3 = text3.ToCharArray(); 25 char[] t4 = text4.ToCharArray(); 26 27 ReverseArrayByXor(t3); 28 ReverseArrayByXor(t4); 29 30 string s3 = new string(t3); 31 string s4 = new string(t4); 32 Console.WriteLine(s3); 33 Console.WriteLine(s4); 34 35 Console.ReadKey(); 36 } 37 38 static void ReversePartOfString(char[] s, int begin, int length) 39 { 40 char temp; 41 for (int i = begin, j = begin + length - 1; i < j; i++, j--) 42 { 43 temp = s[i]; 44 s[i] = s[j]; 45 s[j] = temp; 46 } 47 } 48 49 static void ReversePartOfStringWithWhile(char[] s, int begin, int length) 50 { 51 // actually, use while is same with use for loop 52 // which one looks better? 53 char temp; 54 int i = begin; 55 int j = begin + length - 1; 56 while (i < j) 57 { 58 temp = s[i]; 59 s[i] = s[j]; 60 s[j] = temp; 61 i++; 62 j--; 63 } 64 } 65 66 static void ReverseArray(char[] s) 67 { 68 char temp; 69 for (int i = 0, j = s.Length - 1; i < j; i++, j--) 70 { 71 temp = s[i]; 72 s[i] = s[j]; 73 s[j] = temp; 74 } 75 } 76 77 static void ReverseArrayByXor(char[] s) 78 { 79 for (int i = 0, j = s.Length - 1; i < j; i++, j--) 80 { 81 // XOR 2 values bitwise 3 times and they're switched 82 s[i] ^= s[j]; 83 s[j] ^= s[i]; 84 s[i] ^= s[j]; 85 } 86 } 87 } 88 }
字符串左旋算法
给定一个字符串，要求把字符串前面的若干个字符移动到字符串的尾部，如把字符串 "abcdef" 前面的 2 个字符 'a' 和 'b' 移动到字符串的尾部，使得原字符串变成字符串 "cdefab"。要求对长度为 n 的字符串操作的时间复杂度为 O(n)，空间复杂度为 O(1)。
1 using System; 2 3 namespace ConsoleApplication1 4 { 5 class Program 6 { 7 static void Main(string[] args) 8 { 9 string s1 = "abcdefg"; 10 string s2 = "abcdefgh"; 11 12 char[] a1 = s1.ToCharArray(); 13 char[] a2 = s2.ToCharArray(); 14 15 LeftRotateStringByGcd(a1, 2); 16 LeftRotateStringByGcd(a2, 2); 17 18 string str1 = new string(a1); 19 string str2 = new string(a2); 20 Console.WriteLine(str1); 21 Console.WriteLine(str2); 22 23 Console.ReadKey(); 24 } 25 26 static void LeftRotateString(char[] s, int m) 27 { 28 ReverseString(s, 0, m - 1); 29 ReverseString(s, m, s.Length - 1); 30 ReverseString(s, 0, s.Length - 1); 31 } 32 33 static void ReverseString(char[] s, int begin, int end) 34 { 35 char temp; 36 int i = begin; 37 int j = end; 38 while (i < j) 39 { 40 temp = s[i]; 41 s[i] = s[j]; 42 s[j] = temp; 43 i++; 44 j--; 45 } 46 } 47 48 static int Gcd(int m, int n) 49 { 50 int k = m % n; 51 if (k == 0) 52 return n; 53 else 54 return Gcd(n, k); 55 } 56 57 static void LeftRotateStringByGcd(char[] s, int m) 58 { 59 int n = s.Length; 60 int g = Gcd(n, m); 61 int e = n / g; 62 63 char temp; 64 for (int i = 0; i < g; i++) 65 { 66 temp = s[i]; 67 68 int j = 0; 69 for (; j < e - 1; j++) 70 { 71 s[(i + j * m) % n] = s[(i + (j + 1) * m) % n]; 72 } 73 74 s[(i + j * m) % n] = temp; 75 } 76 } 77 } 78 }
字符串右旋算法
给定一个字符串，要求把字符串后面的若干个字符移动到字符串的头部，如把字符串 "abcdef" 后面的 2 个字符 'e' 和 'f' 移动到字符串的头部，使得原字符串变成字符串 "efabcd"。要求对长度为 n 的字符串操作的时间复杂度为 O(n)，空间复杂度为 O(1)。
1 using System; 2 3 namespace ConsoleApplication1 4 { 5 class Program 6 { 7 static void Main(string[] args) 8 { 9 string s3 = "abcdefg"; 10 string s4 = "abcdefgh"; 11 12 char[] a3 = s3.ToCharArray(); 13 char[] a4 = s4.ToCharArray(); 14 15 RightRotateString(a3, 2); 16 RightRotateString(a4, 2); 17 18 string str3 = new string(a3); 19 string str4 = new string(a4); 20 Console.WriteLine(str3); 21 Console.WriteLine(str4); 22 23 Console.ReadKey(); 24 } 25 26 static void RightRotateString(char[] s, int m) 27 { 28 ReverseString(s, 0, s.Length - m - 1); 29 ReverseString(s, s.Length - m, s.Length - 1); 30 ReverseString(s, 0, s.Length - 1); 31 } 32 33 static void ReverseString(char[] s, int begin, int end) 34 { 35 char temp; 36 int i = begin; 37 int j = end; 38 while (i < j) 39 { 40 temp = s[i]; 41 s[i] = s[j]; 42 s[j] = temp; 43 i++; 44 j--; 45 } 46 } 47 } 48 }
字符串旋转匹配算法
给定两个字符串 s1 和 s2，如何判断 s1 是 s2 的一个旋转版本？
1 using System; 2 3 namespace ConsoleApplication1 4 { 5 class Program 6 { 7 static void Main(string[] args) 8 { 9 // Given two string s1 and s2 10 // how will you check if s1 is a rotated version of s2 ? 11 12 string s1 = "tackoverflows"; 13 string s2 = "ackoverflowst"; 14 string s3 = "overflowstack"; 15 string s4 = "stackoverflwo"; 16 17 string pattern = "stackoverflow"; 18 19 Console.WriteLine(string.Format("{0}, {1}, {2}", s1, pattern, CheckRotation(s1, pattern))); 20 Console.WriteLine(string.Format("{0}, {1}, {2}", s2, pattern, CheckRotation(s2, pattern))); 21 Console.WriteLine(string.Format("{0}, {1}, {2}", s3, pattern, CheckRotation(s3, pattern))); 22 Console.WriteLine(string.Format("{0}, {1}, {2}", s4, pattern, CheckRotation(s4, pattern))); 23 24 Console.ReadKey(); 25 } 26 27 static bool CheckRotation(string s1, string s2) 28 { 29 return s1.Length == s2.Length 30 && (s1 + s1).IndexOf(s2) != -1; 31 } 32 } 33 }
字符串包含算法
给定两个分别由字母组成的字符串 s1 和字符串 s2，如何最快地判断字符串 s2 中所有字母是否都在字符串 s1 里？
1 using System; 2 3 namespace ConsoleApplication1 4 { 5 class Program 6 { 7 static void Main(string[] args) 8 { 9 string s1 = "abcdefg"; 10 string s2 = "cfx"; 11 12 char[] a1 = s1.ToCharArray(); 13 char[] a2 = s2.ToCharArray(); 14 15 Console.WriteLine( 16 string.Format("{0}, {1}, {2}", s1, s2, IsContainAllChars(a1, a2))); 17 18 Console.ReadKey(); 19 } 20 21 // 给定两个分别由字母组成的字符串a和字符串b 22 // 判断字符串b中所有字母是否都在字符串a里？ 23 // 时间复杂度O(n + m)，空间复杂度O(1) 24 static bool IsContainAllChars(char[] a, char[] b) 25 { 26 int hash = 0; 27 for (int i = 0; i < a.Length; ++i) 28 { 29 hash |= (1 << (a[i] - 'A')); 30 } 31 32 for (int i = 0; i < b.Length; ++i) 33 { 34 if ((hash & (1 << (b[i] - 'A'))) == 0) 35 { 36 return false; 37 } 38 } 39 40 return true; 41 } 42 } 43 }
字符串原地替换算法
将字符串 s1 中的某字符 p 全部替换成字符串 s2。假设 s1 字符数组尾部有足够的空间存放新增字符。
1 using System; 2 using System.Collections.Generic; 3 4 namespace AlgorithmTesting 5 { 6 class Program 7 { 8 static void Main(string[] args) 9 { 10 // 假设 s1 有足够的冗余空间 11 char[] s1 = new char[100]; 12 for (int i = 0; i < 9; i = i + 3) 13 { 14 s1[i] = 'a'; 15 s1[i + 1] = 'b'; 16 s1[i + 2] = 'c'; 17 } 18 19 Console.WriteLine(new string(s1)); 20 ReplaceChars(s1, 9, 'b', "%&$".ToCharArray()); 21 Console.WriteLine(new string(s1)); 22 Console.ReadKey(); 23 } 24 25 // 将字符串 s1 中的某字符 p 替换成字符串 s2 26 static void ReplaceChars(char[] s1, int s1Length, char p, char[] s2) 27 { 28 int count = 0; 29 for (int i = 0; i < s1.Length; i++) 30 { 31 if (s1[i] == p) 32 count++; 33 } 34 35 int newLength = s1Length + count * (s2.Length - 1); 36 37 // 从尾部开始编辑，从后向前操作，无须担心覆写原数据 38 for (int i = s1Length - 1; i >= 0; i--) 39 { 40 if (s1[i] == p) 41 { 42 for (int j = 0; j < s2.Length; j++) 43 { 44 s1[newLength - s2.Length + j] = s2[j]; 45 } 46 newLength = newLength - s2.Length; 47 } 48 else 49 { 50 s1[newLength - 1] = s1[i]; 51 newLength = newLength - 1; 52 } 53 } 54 } 55 } 56 }
字符串压缩算法
给定字符串 s，要求将连续出现的字符压缩至字符和数量，并返回新的字符串。
比如：s = "aabccccaaa"，则压缩后的字符串为 s2 = "a2b1c4a3"。
1 using System; 2 using System.Collections.Generic; 3 4 namespace AlgorithmTesting 5 { 6 class Program 7 { 8 static void Main(string[] args) 9 { 10 string s1 = "aabccccaaa"; 11 Console.WriteLine(s1); 12 char[] s2 = Compress(s1.ToCharArray()); 13 Console.WriteLine(new string(s2)); 14 15 string s3 = "aabccdeeaa"; 16 Console.WriteLine(s3); 17 char[] s4 = Compress(s3.ToCharArray()); 18 Console.WriteLine(new string(s4)); 19 20 Console.ReadKey(); 21 } 22 23 static char[] Compress(char[] s) 24 { 25 // 如果压缩后比原来还长，则不必压缩 26 int size = CountCompression(s); 27 if (size >= s.Length) 28 return s; 29 30 // 根据计算的压缩后长度生成数组 31 char[] compressed = new char[size]; 32 33 int index = 0; 34 char last = s[0]; 35 int count = 1; 36 for (int i = 1; i < s.Length; i++) 37 { 38 if (s[i] == last) // 找到重复字符 39 { 40 count++; 41 } 42 else 43 { 44 // 当前字符处理完毕 45 index = AppendChar(compressed, last, index, count); 46 47 // 处理下一个字符 48 last = s[i]; 49 count = 1; 50 } 51 } 52 53 // 添加最后一个字符 54 index = AppendChar(compressed, last, index, count); 55 56 return compressed; 57 } 58 59 static int AppendChar(char[] array, char c, int index, int count) 60 { 61 array[index] = c; 62 index++; 63 64 char[] countString = count.ToString().ToCharArray(); 65 66 for (int i = 0; i < countString.Length; i++) 67 { 68 array[index] = countString[i]; 69 index++; 70 } 71 72 return index; 73 } 74 75 static int CountCompression(char[] s) 76 { 77 if (s == null || s.Length == 0) 78 return 0; 79 80 // 计算压缩后的长度 81 int size = 0; 82 83 char last = s[0]; 84 int count = 1; 85 for (int i = 0; i < s.Length; i++) 86 { 87 if (s[i] == last) // 找到重复字符 88 { 89 count++; 90 } 91 else 92 { 93 // 当前字符处理完毕 94 size += 1 + count.ToString().ToCharArray().Length; 95 96 // 处理下一个字符 97 last = s[i]; 98 count = 1; 99 } 100 } 101 102 size += 1 + count.ToString().ToCharArray().Length; 103 104 return size; 105 } 106 } 107 }
字符串变位词检测算法
给定字符串 s1 和 s2，判断是否能够将 s1 中的字符重新排列后变成 s2。假设字符全部为小写 a-z 字符，字符串中没有空格。
变位词（anagram）：是由变换某个词或短语的字母顺序而构成的新的词或短语。
1 using System; 2 using System.Collections.Generic; 3 4 namespace AlgorithmTesting 5 { 6 class Program 7 { 8 static void Main(string[] args) 9 { 10 Console.WriteLine(IsPermutation( 11 "hello".ToCharArray(), "ehollu".ToCharArray())); 12 Console.WriteLine(IsPermutation( 13 "hello".ToCharArray(), "eholu".ToCharArray())); 14 Console.WriteLine(IsPermutation( 15 "hello".ToCharArray(), "eholl".ToCharArray())); 16 Console.ReadKey(); 17 } 18 19 static bool IsPermutation(char[] s1, char[] s2) 20 { 21 if (s1.Length != s2.Length) 22 return false; 23 24 int[] letters = new int[256]; 25 for (int i = 0; i < s1.Length; i++) 26 { 27 letters[s1[i]]++; 28 } 29 30 for (int i = 0; i < s2.Length; i++) 31 { 32 letters[s2[i]]--; 33 if (letters[s2[i]] < 0) 34 return false; 35 } 36 37 return true; 38 } 39 } 40 }
字符串删除算法
给定两个分别由字母组成的字符串 s1 和字符串 s2，将字符串 s2 中所有字符都在字符串 s1 中删除？
1 using System; 2 3 namespace ConsoleApplication1 4 { 5 class Program 6 { 7 static void Main(string[] args) 8 { 9 string text = "cdacbcdefabcdef"; 10 string pattern = "ab"; 11 12 char[] t = text.ToCharArray(); 13 char[] p = pattern.ToCharArray(); 14 15 // generate hash table of pattern 16 bool[] hash = new bool[256]; 17 for (int i = 0; i < p.Length; i++) 18 { 19 hash[p[i]] = true; 20 } 21 22 // compare text chars exist in pattern 23 int faster = 0; 24 int slower = 0; 25 while (faster < t.Length) 26 { 27 // want to save some space 28 if (!hash[t[faster]]) 29 { 30 t[slower] = t[faster]; 31 faster++; 32 slower++; 33 } 34 else 35 { 36 faster++; 37 } 38 } 39 40 // make string 41 string s = new string(t, 0, slower); 42 43 Console.WriteLine(s); 44 Console.ReadKey(); 45 } 46 } 47 }
字符串转整数算法
输入一个由数字组成的字符串，把它转换成整数并输出。例如：输入字符串 "123"，输出整数 123。
1 using System; 2 3 namespace ConsoleApplication1 4 { 5 class Program 6 { 7 static void Main(string[] args) 8 { 9 // good 10 Console.WriteLine(string.Format("{0}, {1}", 11 "12345", StringToInt32("12345".ToCharArray()))); 12 Console.WriteLine(string.Format("{0}, {1}", 13 "-12345", StringToInt32("-12345".ToCharArray()))); 14 15 // max 16 Console.WriteLine(string.Format("{0}, {1}", 17 "2147483647", StringToInt32("2147483647".ToCharArray()))); 18 Console.WriteLine(string.Format("{0}, {1}", 19 "-2147483648", StringToInt32("-2147483648".ToCharArray()))); 20 21 // overflow 22 Console.WriteLine(string.Format("{0}, {1}", 23 "21474836470", StringToInt32("21474836470".ToCharArray()))); 24 Console.WriteLine(string.Format("{0}, {1}", 25 "-21474836480", StringToInt32("-21474836480".ToCharArray()))); 26 27 Console.ReadKey(); 28 } 29 30 static int StringToInt32(char[] s) 31 { 32 // do you need handle space? 33 // do you need handle bad char? 34 35 // check string null 36 if (s.Length == 0) 37 { 38 return 0; 39 } 40 41 int value = 0; 42 int i = 0; 43 44 // check positive or negative 45 int sign = 1; 46 if (s[0] == '+' || s[0] == '-') 47 { 48 if (s[0] == '-') 49 sign = -1; 50 i++; 51 } 52 53 while (i < s.Length) 54 { 55 int c = s[i] - '0'; 56 57 // handle overflow 58 if (sign > 0 59 && (value > int.MaxValue / 10 60 || (value == int.MaxValue / 10 61 && c >= int.MaxValue % 10))) 62 { 63 value = int.MaxValue; 64 break; 65 } 66 else if (sign < 0 67 && (value > -(int.MinValue / 10) 68 || (value == -(int.MinValue / 10) 69 && c >= -(int.MinValue % 10)))) 70 { 71 value = int.MinValue; 72 break; 73 } 74 75 // calculate the value based on 10 times 76 value = value * 10 + c; 77 78 i++; 79 } 80 81 return sign > 0 82 ? value 83 : value == int.MinValue ? value : -value; 84 } 85 } 86 }
字符串全排列算法
输入一个字符串，打印出该字符串中字符的所有排列。
例如：输入字符串 "abc"，则输出由字符 'a', 'b', 'c' 所能排列出来的所有字符串：abc, acb, bac, bca, cab, cba。
1 using System; 2 3 namespace ConsoleApplication1 4 { 5 class Program 6 { 7 static void Main(string[] args) 8 { 9 // 要求首次输入是有序的，否则需要排序 10 CalculateAllPermutations("abc".ToCharArray()); 11 12 Console.ReadKey(); 13 } 14 15 static void CalculateAllPermutations(char[] s) 16 { 17 // 输出当前排列 18 Console.WriteLine(new string(s)); 19 20 int i, j; 21 22 // 找到排列中最右一个升序的首位位置 i 23 for (i = s.Length - 2; (i >= 0) && (s[i] >= s[i + 1]); --i) ; 24 25 // 已经找到所有排列 26 if (i < 0) return; 27 28 // 找到排列中第 i 位右边最后一个比 s[i] 大的位置 j 29 for (j = s.Length - 1; (j > i) && (s[j] <= s[i]); --j) ; 30 31 // 交换 s[i]，s[j] 32 Swap(s, i, j); 33 34 // 将第 i + 1 位到最后的部分反转 35 Reverse(s, i + 1, s.Length - 1); 36 37 // 继续下一次排列 38 CalculateAllPermutations(s); 39 } 40 41 static void Swap(char[] s, int i, int j) 42 { 43 char temp = s[i]; 44 s[i] = s[j]; 45 s[j] = temp; 46 } 47 48 static void Reverse(char[] s, int begin, int end) 49 { 50 char temp; 51 int i = begin; 52 int j = end; 53 while (i < j) 54 { 55 temp = s[i]; 56 s[i] = s[j]; 57 s[j] = temp; 58 i++; 59 j--; 60 } 61 } 62 } 63 }
字符串字典序组合算法
输入一个字符串，字符串里的字符是互不相同的，打印出该字符串中字符按照字典序输出所有的组合。
例如：输入字符串 "ab"，则输出由字符 'a', 'b' 所能排列出来的所有字符串：aa, ab, ba, bb。
1 using System; 2 3 namespace ConsoleApplication1 4 { 5 class Program 6 { 7 static void Main(string[] args) 8 { 9 // 要求字符是不同的，否则需要去重 10 // 要求输入是有序的，否则需要排序 11 CalculateRepeatablePermutations("abc".ToCharArray(), new char[3], 0); 12 13 Console.ReadKey(); 14 } 15 16 static void CalculateRepeatablePermutations(char[] s, char[] permutation, int p) 17 { 18 if (p == s.Length) 19 { 20 Console.WriteLine(new string(permutation)); 21 } 22 else 23 { 24 for (int i = 0; i < s.Length; ++i) 25 { 26 permutation[p] = s[i]; 27 CalculateRepeatablePermutations(s, permutation, p + 1); 28 } 29 } 30 } 31 } 32 }
字符串的（括号）生成算法
输出 n 对括号的全部有效组合。
1 using System; 2 using System.Collections.Generic; 3 4 namespace AlgorithmTesting 5 { 6 class Program 7 { 8 static void Main(string[] args) 9 { 10 List<string> parenList = GenerateParens(3); 11 foreach (var item in parenList) 12 { 13 Console.WriteLine(item); 14 } 15 16 Console.ReadKey(); 17 } 18 19 static List<string> GenerateParens(int count) 20 { 21 char[] str = new char[count * 2]; 22 List<string> list = new List<string>(); 23 AddParen(list, count, count, str, 0); 24 return list; 25 } 26 27 static void AddParen( 28 List<string> list, 29 int leftRem, 30 int rightRem, 31 char[] str, 32 int count) 33 { 34 // 无效状态 35 if (leftRem < 0 || rightRem < leftRem) 36 return; 37 38 // 无括号可用 39 if (leftRem == 0 && rightRem == 0) 40 { 41 string s = new string(str); 42 list.Add(s); 43 } 44 else 45 { 46 // 还有左括号可用 47 if (leftRem > 0) 48 { 49 str[count] = '('; 50 AddParen(list, leftRem - 1, rightRem, str, count + 1); 51 } 52 53 // 还有右括号可用 54 if (rightRem > leftRem) 55 { 56 str[count] = ')'; 57 AddParen(list, leftRem, rightRem - 1, str, count + 1); 58 } 59 } 60 } 61 } 62 }
