作者：whisper

链接：http://proprogrammar.com:443/article/224

声明：请尊重原作者的劳动，如需转载请注明出处

    正如我们在概览中提到的那样，字符串是一个由字符构成的数组。

    本章节中，我们将深入研究字符串。完成本章后，你将：

• 熟悉字符串中的基本操作，尤其是在数组中没有的独特操作；
• 理解不同比较函数之间的区别；
• 判断字符串在你最喜欢的语言中是否为不可变的并了解这个特性带来的影响；
• 能够解决与字符串相关的基本问题。

     字符串简介

    字符串实际上是一个 unicode 字符数组。你可以执行几乎所有我们在数组中使用的操作，自己试试看吧。

    然而，二者之间还是存在一些区别。在这篇文章中，我们将介绍一些在处理字符串时应该注意的问题。这些特性在不同的语言之间可能有很大不同。

    比较函数

    字符串有它自己的比较函数（我们将在下面的代码中向你展示比较函数的用法）。

    然而，存在这样一个问题：

我们可以用 “==” 来比较两个字符串吗？

     这取决于下面这个问题的答案：

我们使用的语言是否支持运算符重载？

1. 如果答案是 yes （例如 C++）。我们可以使用 “==” 来比较两个字符串。
2. 如果答案是 no （例如 Java），我们可能无法使用 “==” 来比较两个字符串。当我们使用  “==” 时，它实际上会比较这两个对象是否是同一个对象。

    让我们运行下面的例子并比较结果：

// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
        // initialize
        String s1 = "Hello World";
        System.out.println("s1 is \"" + s1 + "\"");
        String s2 = s1;
        System.out.println("s2 is another reference to s1.");
        String s3 = new String(s1);
        System.out.println("s3 is a copy of s1.");
        // compare using '=='
        System.out.println("Compared by '==':");
        // true since string is immutable and s1 is binded to "Hello World"
        System.out.println("s1 and \"Hello World\": " + (s1 == "Hello World"));
        // true since s1 and s2 is the reference of the same object
        System.out.println("s1 and s2: " + (s1 == s2));
        // false since s3 is refered to another new object
        System.out.println("s1 and s3: " + (s1 == s3));
        // compare using 'equals'
        System.out.println("Compared by 'equals':");
        System.out.println("s1 and \"Hello World\": " + s1.equals("Hello World"));
        System.out.println("s1 and s2: " + s1.equals(s2));
        System.out.println("s1 and s3: " + s1.equals(s3));
        // compare using 'compareTo'
        System.out.println("Compared by 'compareTo':");
        System.out.println("s1 and \"Hello World\": " + (s1.compareTo("Hello World") == 0));
        System.out.println("s1 and s2: " + (s1.compareTo(s2) == 0));
        System.out.println("s1 and s3: " + (s1.compareTo(s3) == 0));
    }
}

    是否可变

    不可变意味着一旦字符串被初始化，你就无法改变它的内容。

1. 在某些语言（如 C ++）中，字符串是可变的。 也就是说，你可以像在数组中那样修改字符串。
2. 在其他一些语言（如  Java）中，字符串是不可变的。 此特性将带来一些问题。 我们将在下一篇文章中阐明问题和解决方案。

    你可以通过测试修改操作来确定你喜欢的语言中的字符串是否可变。这里有一个示例：

// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
        String s1 = "Hello World";
        s1[5] = ',';
        System.out.println(s1);
    }
}

    额外操作

    与数组相比，我们可以对字符串执行一些额外的操作。这里有一些例子：

// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
        String s1 = "Hello World";
        // 1. concatenate
        s1 += "!";
        System.out.println(s1);
        // 2. find
        System.out.println("The position of first 'o' is: " + s1.indexOf('o'));
        System.out.println("The position of last 'o' is: " + s1.lastIndexOf('o'));
        // 3. get substring
        System.out.println(s1.substring(6, 11));
    }
}

    你应该了解这些内置操作的时间复杂度。

    例如，如果字符串的长度是 N，那么查找操作和子字符串操作的时间复杂度是 O(N)。

    此外，在字符串不可变的语言中，你应该额外小心连接操作（我们将在下一篇文章中解释这一点）。

    在计算解决方案的时间复杂度时，不要忘记考虑内置操作的时间复杂度。

    不可变字符串 —— 问题和解决方案

    在上一篇文章中，您应该已经知道您喜欢的语言中的字符串是否为不可变的。如果字符串是不可变的，则会带来一些问题。希望我们也能在最后提供解决方案。

    修改操作

    显然，不可变字符串无法被修改。哪怕你只是想修改其中的一个字符，也必须创建一个新的字符串。

    小心 Java 中的字符串

    你应该非常小心字符串连接。让我们来看一个在 for 循环中重复进行字符串连接的例子：

// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
        String s = "";
        int n = 10000;
        for (int i = 0; i < n; i++) {
            s += "hello";
        }
    }
}

    请注意对于 Java 来说字符串连接有多慢？ 另一方面，在 C++ 中没有明显的性能影响。

    在 Java 中，由于字符串是不可变的，因此在连接时首先为新字符串分配足够的空间，复制旧字符串中的内容并附加到新字符串。

    因此，总时间复杂度将是：

   5 + 5 × 2 + 5 × 3 + … + 5 × n
= 5 × (1 + 2 + 3 + … + n)
= 5 × n × (n + 1) / 2,

    也就是 O(n2)。

    解决方案

    如果你希望你的字符串是可变的，这里有一些替代方案：

    1. 如果你确实希望你的字符串是可变的，则可以将其转换为字符数组。

// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
        String s = "Hello World";
        char[] str = s.toCharArray();
        str[5] = ',';
        System.out.println(str);
    }
}

    2. 如果你经常必须连接字符串，最好使用一些其他的数据结构，如 StringBuilder 。 以下代码以 O(n) 的复杂度运行。

// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
        int n = 10000;
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < n; i++) {
            str.append("hello");
        }
        String s = str.toString();
    }
}

    算法说明

    二进制求和

给定两个二进制字符串，返回他们的和（用二进制表示）。

输入为非空字符串且只包含数字 1 和 0。

示例 1:

输入: a = "11", b = "1"
输出: "100"

示例 2:

输入: a = "1010", b = "1011"
输出: "10101"

 

// 想法，先对齐两数，短的高位补0，运算：三个数，原始两个数加进位，00 0得0进0；00 1， 01 0, 10 0得1进0；10 1, 01 1, 11 0得0进1, 11 1得1进1
    // 虽然有点复杂但思路很清楚（灵感来源：计算机组成原理中的定点数的运算）
    public String addBinary(String a, String b) {
        // 想法1：用JDK内置api :问题，超出范围
        // return Integer.toBinaryString(Integer.valueOf(a, 2) + Integer.valueOf(b, 2));
        char ac, bc, carry = '0';
        int len;
        StringBuilder sb = new StringBuilder();
        
        if(a.length() > b.length()){
            len = a.length() - b.length();
            for(int i = 0; i < len; i++){
                sb.append("0");
            }
            
            b = sb.toString() + b;
        }else if(b.length() > a.length()){
            len = b.length() - a.length();
            for(int i = 0; i < len; i++){
                sb.append("0");
            }
            
            a = sb.toString() + a;
        }
        
        sb.setLength(0);
        for(int i = a.length() - 1; i >= 0; i--){
            ac = a.charAt(i);
            bc = b.charAt(i);
            
            if((ac + bc + carry) == 3 * '0'){
                carry = '0';
                sb.insert(0, "0");
            }else if((ac + bc + carry) == 3 * '0' + 1){
                carry = '0';
                sb.insert(0, "1");
            }else if((ac + bc + carry) == 3 * '0' + 2){
                carry = '1';
                sb.insert(0, "0");
            }else if((ac + bc + carry) == 3 * '0' + 3){
                carry = '1';
                sb.insert(0, "1");
            }
        }
        
        if(carry == '1'){
            sb.insert(0, "1");
        }
        
        return sb.toString();
    }

     算法有点复杂但思路很清晰，几个if..else可以优化掉

     下面看一个更好的算法

public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int i = a.length() - 1;
        int j = b.length() - 1;
        int remainder = 0;
        while (i >= 0 || j >= 0) {
            int sum = remainder;
            if (i >= 0) sum += a.charAt(i--) - '0';
            if (j >= 0) sum += b.charAt(j--) - '0';
            sb.append(sum % 2);
            remainder = sum / 2;
        }
        if (remainder != 0) {
            sb.append(remainder);
        }
        return sb.reverse().toString();
    }

    没有我的那些if...else判断，而是用%与/，代码更加紧凑，更加简洁

    实现 strStr()

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。

示例 1:

输入: haystack = "hello", needle = "ll"
输出: 2

示例 2:

输入: haystack = "aaaaa", needle = "bba"
输出: -1

说明:

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

// 想法：直接用String中的indexOf函数
    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }

    直接用java的api即可，效率很高

    最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"

示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明:

所有输入只包含小写字母 a-z 。

// 想法：用indexOf，依次取第一个元素的前1，2，3...个字符的子串，看是否是其它元素的前缀
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0){
            return "";
        }

        int resultLen = 0;
        String first = strs[0];
        
        breakLoop:
        while(first.length() >= resultLen + 1){
            for(int i = 1; i < strs.length; i++){
                if(strs[i].length() < resultLen + 1 || strs[i].charAt(resultLen) != first.charAt(resultLen)){
                    break breakLoop;
                }
            }
            
            resultLen++;
        }
        
        return first.substring(0, resultLen);
    }

    下面看另一种算法

public String longestCommonPrefix(String[] strs) {      

        if (strs.length == 0) {
            return "";
        } else if(strs.length == 1) {
            return strs[0];
        } else { 
            String strSmall = strs[0];
            for (int i = 1; i < strs.length; i++) {
                if (strs[i].length() < strSmall.length()) {
                    strSmall = strs[i];
                }
            }
                       
            for (int i = strSmall.length(); i > 0; i--) {
                String prefix = strSmall.substring(0,i);
                boolean find = true;
                for (int j = 0; j < strs.length; j++) {
                    if (!strs[j].startsWith(prefix)) {
                        find = false;
                        break;
                    }
                }
                if (find) {
                    return prefix.toString();
                }                 
            } 
            return "";
        }     
    }

    先找出最短的元素，然后由长到短进行判断，充分利用了String原有的api

亲爱的读者：有时间可以点赞评论一下