内容摘要

字符串是程序中使用最广的数据结构之一,本文以大量的示例和代码讲解了字符串的常见算法,包括大小写转换、Atoi、宝石与石头(leetcode第771题),希望对大家有所帮助。
如果您觉得有用,也欢迎将本文推荐给您的朋友。

什么是字符串

字符串(string),是由零个或多个字符组成的有限序列,是编程中最重要的数据结构之一。
详细定义请参见维基百科

你的字符串是immutable吗?

immutable意味着不可改变,是一个常量。比如光在真空中的速度就是一个宇宙级的常量,又比如数字"3”,也是一个常量。
但是变量是可以改变指向的,比如name = “andy”,“andy"这个字符串常量是不可改变的,但是name变量可以改变指向,比如name = “jack”。

字符串在各语言中是否是immutable

  • 在java, c#, javascript, python, go中,string是immutable的。
  • 在ruby, php中,string是mutable。
  • c语言本身并没有string类型,而只有char *类型或char数组,我们可用使用char *来实现string,当然它是mutable的; c++中的string是mutable的,虽然可以添加const来限制其为immutable,但是可以很容易的通过const_cast移除掉,因此c++ string中的immutability是比较弱的。
    更详细的分析请参见Are your strings immutable?

字符串常见算法

字符串算法最丰富的数据结构之一,凝聚着很多计算机科学家及工程师智慧的结晶,也是许多有意思的问题及解决方案,这里先列举几个基础的字符串算法,后续本专栏也会持续推出更多的字符串算法,比如字符串反转、字符串匹配,字符串查询,异位词,回文串等,敬请期待。

大小写转换

大小写转换是字符串中常见的操作之一,经常用于数据分析或协议转换中,用来标准化各种输入。这里以Java为例进行讲解,其他语言原理类似。

解法1:库函数

比如Java的String提供了toLowerCase函数,可以直接调用。

1
2
3
4
5
class ToLowerCase709 {
  public String toLowerCase(String str) {
    return str.toLowerCase();
  }
}

解法2:AscII码转换

有时候,语言本身并没有提供相应String大小写转换的功能,比如C语言,或在面试中,要求面试者自己实现相应功能的时候,这时我们就不得不自己实现了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * 大小写字母的ASCII码
 * [a,z] = [97,122]
 * [A,Z] = [65,90]
 */
public class ToLowerCase709 {
  // 转换为小写
  public String toLowerCase(String str) {
    // 参数合法性校验
    if (str == null) {
      return null;
    }

    int index = 0;
    StringBuilder result = new StringBuilder();
    while (index < str.length()) {
      if (str.charAt(index) >= 'A' && str.charAt(index) <= 'Z') {
        result.append((char)(str.charAt(index) + ('a' - 'A')));
      } else {
        result.append(str.charAt(index));
      }

      index++;
    }

    return result.toString();
  }
}

解法3:二进制

基本解法和解法2类似,在转换的时候可以通过位运算来加速

1
大写变小写: ASCII码 |= 32
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * 大小写字母的ASCII码
 * [a,z] = [97,122]
 * [A,Z] = [65,90]
 */
public class ToLowerCase709 {
  // 转换为小写
  public String toLowerCase(String str) {
    // 参数合法性校验
    if (str == null) {
      return null;
    }

    int index = 0;
    StringBuilder result = new StringBuilder();
    while (index < str.length()) {
      if (str.charAt(index) >= 'A' && str.charAt(index) <= 'Z') {
        result.append((char)(str.charAt(index) | (char)32));
      } else {
        result.append(str.charAt(index));
      }

      index++;
    }

    return result.toString();
  }
}

Atoi,字符串转整形(ascii to integer)

Atoi也比较简单,主要就是扫描字符串,每扫描一位,就相当于整形中乘了一个10,在扫描过程中注意空格及符号位的处理。由于string底层实现都是字符数组,因此每一步的越界检查也需要特别小心。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
public class MyAtoi8 {
  // atoi, 转换失败返回0
  public int myAtoi(String str) {
    int total = 0;
    int sign = 1;
    int index = 0;

    if (str == null || str.isEmpty()) {
      return 0;
    }

    // left trim
    while (index < str.length() && str.charAt(index) == ' ') {
      index++;
    }

    // 符号位处理
    if (index < str.length() && (str.charAt(index) == '-' || str.charAt(index) == '+')) {
      sign = str.charAt(index) == '-' ? -1 : 1;
      index++;
    }

    // 扫描字符串
    while (index < str.length()) {
      int d = str.charAt(index) - '0';
      if (d < 0 || d > 9) {
        break;
      }

      // 最大值处理
      if (Integer.MAX_VALUE / 10 < total || Integer.MAX_VALUE / 10 == total
              && Integer.MAX_VALUE % 10 < d) {
        return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
      }

      total = total * 10 + d;
      index++;
    }

    return total * sign;
  }

  public static void main(String[] args) {
    String s0 = "+1345";
    MyAtoi8 so = new MyAtoi8();
    System.out.println(so.myAtoi(s0));

    String s1 = null;
    System.out.println(so.myAtoi(s1));

    String s2 = "-234289884f89fh4";
    System.out.println(so.myAtoi(s2));

    String s3= "3237598394989349893893948593953495435";
    System.out.println(so.myAtoi(s3));
    
    String s4 = "!!r3r3";
    System.out.println(so.myAtoi(s4));
    
    String s5 = "       123678";
    System.out.println(so.myAtoi(s5));
    
    String s6 = "";
    System.out.println(so.myAtoi(s6));
    
    String s7 = " ";
    System.out.println(so.myAtoi(s7));
  }
}

输出:

1
2
3
4
5
6
7
8
1345
0
-234289884
2147483647
0
123678
0
0

宝石与石头

接下来我们来看看一个比较有意思的题目: 给定字符串J 代表石头中宝石的类型,和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型,你想知道你拥有的石头中有多少是宝石。
J 中的字母不重复,J 和 S中的所有字符都是字母。字母区分大小写,因此"a"和"A"是不同类型的石头。 示例 1:

1
2
输入: J = "aA", S = "aAAbbbb"
输出: 3

示例 2:

1
2
输入: J = "z", S = "ZZ"
输出: 0

注意:

1
2
S  J 最多含有50个字母
J 中的字符不重复

题目来自leetcode第771题:

https://leetcode-cn.com/problems/jewels-and-stones/

解法分析

  • 暴力法:可以遍历S,然后针对S中的每个字母,去遍历J,看看这个字母是不是在J中,如果是,则当前这个字母就代表一个宝石;这种解法的时间复杂度为O(M * N)(假设J的长度是M,S的长度是N)。
  • 使用hash表加速:暴力法每次都要遍历J,可以把J中的字母存放在hash表中,这样扫描S中的每个字母的时候,可以在O(1)的时间内返回其是否在J中;时间复杂度为O(N),由于使用了额外的数据结构,空间复杂度为O(M)。
  • 使用字母表加速:由于J和S的所有字符都是字母,可以用一个字符数组把J中的字符存起来,并把J中有的字母相应的位置置1,这样在扫描S的时候,也可以在O(1)的时间内进行判断。

这种利用字母表的思想,在字符串的计算中非常常见,使用得好的话,经常可以省去不必要的遍历操作,这也是空间换时间思维的一种典型应用。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 字母表加速解法
public class NumJewelsInStones771 {
  public int numJewelsInStones(String J, String S) {
    int[] alphabet = new int[52];
    for (char c : J.toCharArray()) {
      if (c >= 'A' && c <= 'Z') {
        alphabet[c - 'A'] = 1;
      } else {
        alphabet[c - 'a' + 26] = 1;
      }
    }

    // 宝石个数
    int count = 0;
    for (char c : S.toCharArray()) {
      if (c >= 'A' && c <= 'Z' && alphabet[c - 'A'] == 1) {
        count++;
      } else if (c >= 'a' && c <= 'z' && alphabet[c - 'a' + 26] == 1) {
        count++;
      }
    }

    return count;
  }
}

总结

今天我们探讨了字符串的定义,字符串的可变性以及常见的一些字符串的操作;字符串的基础使用看起来简单,其实是非常考验大家编程功底的地方,怎样把代码写的简单高效,需要在平时工作中不断的去发掘和练习。