字符串面试题总结（终极版）

迷南。 2022-12-23 11:10 132阅读 0赞

### 文章目录 ###

*   *  有效的字母异位词
     *   *  解法
     *  最长回文串
     *   *  解法
     *  同构字符串
     *   *  解法
     *  回文子串
     *   *  解法
     *  回文数
     *   *  解法
     *  计数二进制子串
     *   *  解法
     *  剑指 Offer 58 - I. 翻转单词顺序
     *   *  解法
     *  剑指 Offer 58 - II. 左旋转字符串
     *   *  解法
     *  剑指 Offer 67. 把字符串转换成整数
     *   *  解法

## 有效的字母异位词 ##

[242. 有效的字母异位词][242.]

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1:
    
    输入: s = "anagram", t = "nagaram"
    输出: true
    示例 2:
    
    输入: s = "rat", t = "car"
    输出: false
    说明:
    你可以假设字符串只包含小写字母。
    
    进阶:
    如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

### 解法 ###

class Solution {
        
        public boolean isAnagram(String s, String t) {
        
            char[] array = new char[26];
            for (char c : s.toCharArray()) {
        
                array[c - 'a']++;
            }
            for (char c : t.toCharArray()) {
        
                array[c - 'a']--;
            }
            for (char c : array) {
        
                if (c != 0) {
        
                    return false;
                }
            }
            return true;
        }
    }

## 最长回文串 ##

[409. 最长回文串][409.]

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。

在构造过程中，请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。

注意:  
假设字符串的长度不会超过 1010。

示例 1:

输入:  
“abccccdd”

输出:  
7

解释:  
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

### 解法 ###

class Solution {
        
        public int longestPalindrome(String s) {
        
            char[] array = new char[256];
            for (char c : s.toCharArray()) {
        
                array[c]++;
            }
            int res = 0;
            for (char c : array) {
        
                res += (c / 2) * 2;
            }
            if (res < s.length()) {
        
                res++;
            }
            return res;
        }
    }

## 同构字符串 ##

[205. 同构字符串][205.]

给定两个字符串 s 和 t，判断它们是否是同构的。

如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。

所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。

示例 1:

输入: s = “egg”, t = “add”  
输出: true  
示例 2:

输入: s = “foo”, t = “bar”  
输出: false  
示例 3:

输入: s = “paper”, t = “title”  
输出: true  
说明:  
你可以假设 s 和 t 具有相同的长度。

### 解法 ###

class Solution {
        
        public boolean isIsomorphic(String s, String t) {
        
            int[] index1 = new int[256];
            int[] index2 = new int[256];
            for (int i = 0; i < s.length(); i++) {
        
                char sc = s.charAt(i), tc = t.charAt(i);
                if (index1[sc] != index2[tc]) {
        
                    return false;
                }
                index1[sc] = i + 1;
                index2[tc] = i + 1;
            }
            return true;
        }
    }

## 回文子串 ##

[647. 回文子串][647.]

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。

示例 1:

输入: “abc”  
输出: 3  
解释: 三个回文子串: “a”, “b”, “c”.  
示例 2:

输入: “aaa”  
输出: 6  
说明: 6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”.  
注意:

输入的字符串长度不会超过1000。

### 解法 ###

class Solution {
        
        private int count = 0;
        
        public int countSubstrings(String s) {
        
            for (int i = 0; i < s.length(); i++) {
        
                extendSubstrings(s, i, i);
                extendSubstrings(s, i, i + 1);
            }
            return count;
        }
        
        private void extendSubstrings(String s, int start, int end) {
        
            while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
        
                start--;
                end++;
                count++;
            }
        }
    }

## 回文数 ##

[9. 回文数][9.]

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例 1:
    
    输入: 121
    输出: true
    示例 2:
    
    输入: -121
    输出: false
    解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
    示例 3:
    
    输入: 10
    输出: false
    解释: 从右向左读, 为 01 。因此它不是一个回文数。
    进阶:
    
    你能不将整数转为字符串来解决这个问题吗？

### 解法 ###

class Solution {
        
        public boolean isPalindrome(int x) {
        
            if (x == 0) {
        
                return true;
            }
            if (x < 0 || x % 10 == 0) {
        
                return false;
            }
            int right = 0;
            while (x > right) {
        
                right = right * 10 + x % 10;
                x /= 10;
            }
            return x == right || x == right / 10;
        }
    }

## 计数二进制子串 ##

[696. 计数二进制子串][696.]

给定一个字符串 s，计算具有相同数量0和1的非空(连续)子字符串的数量，并且这些子字符串中的所有0和所有1都是组合在一起的。

重复出现的子串要计算它们出现的次数。

示例 1 :
    
    输入: "00110011"
    输出: 6
    解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。
    
    请注意，一些重复出现的子串要计算它们出现的次数。
    
    另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。
    示例 2 :
    
    输入: "10101"
    输出: 4
    解释: 有4个子串：“10”，“01”，“10”，“01”，它们具有相同数量的连续1和0。
    注意：
    
    s.length 在1到50,000之间。
    s 只包含“0”或“1”字符。

### 解法 ###

class Solution {
        
        public int countBinarySubstrings(String s) {
        
            int preLen = 0, curLen = 1, count = 0;
            for (int i = 1; i < s.length(); i++) {
        
                if (s.charAt(i) == s.charAt(i - 1)) {
        
                    curLen++;
                } else {
        
                    preLen = curLen;
                    curLen = 1;
                }
                if (preLen >= curLen) {
        
                    count++;
                }
            }
            return count;
        }
    }

## 剑指 Offer 58 - I. 翻转单词顺序 ##

[剑指 Offer 58 - I. 翻转单词顺序][Offer 58 - I.]

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. “，则输出"student. a am I”。

示例 1：
    
    输入: "the sky is blue"
    输出: "blue is sky the"
    示例 2：
    
    输入: "  hello world!  "
    输出: "world! hello"
    解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
    示例 3：
    
    输入: "a good   example"
    输出: "example good a"
    解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
    
    
    说明：
    
    无空格字符构成一个单词。
    输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
    如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。Copy to clipboardErrorCopied

### 解法 ###

class Solution {
        
        public String reverseWords(String s) {
        
            // 去掉收尾空格
            s = s.trim();  
            int j = s.length() - 1, i = j;
            StringBuilder res = new StringBuilder();
            while (i >= 0) {
        
                // 搜索首个空格
                while (i >= 0 && s.charAt(i) != ' ') {
        
                    i--;
                }
                // 添加单词
                res.append(s.substring(i + 1, j + 1) + " ");
                // 跳过单词间空格
                while (i >= 0 && s.charAt(i) == ' ') {
        
                    i--;
                }
                // j 指向下个单词的尾字符
                j = i;
            }
            return res.toString().trim();
        }
    }

## 剑指 Offer 58 - II. 左旋转字符串 ##

[剑指 Offer 58 - II. 左旋转字符串][Offer 58 - II.]

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

示例 1：
    
    输入: s = "abcdefg", k = 2
    输出: "cdefgab"
    示例 2：
    
    输入: s = "lrloseumgh", k = 6
    输出: "umghlrlose"
    
    
    限制：
    
    1 <= k < s.length <= 10000
    Copy to clipboardErrorCopied

### 解法 ###

class Solution {
        
        public String reverseLeftWords(String s, int n) {
        
            StringBuilder res = new StringBuilder();
            int size = s.length();
            res.append(s.substring(n, size));
            res.append(s.substring(0, n));
            return res.toString();
        }
    }

## 剑指 Offer 67. 把字符串转换成整数 ##

[剑指 Offer 67. 把字符串转换成整数][Offer 67.]

写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0。

说明：

假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 \[−231, 231 − 1\]。如果数值超过这个范围，请返回 INT\_MAX (231 − 1) 或 INT\_MIN (−231) 。

示例 1:
    
    输入: "42"
    输出: 42
    示例 2:
    
    输入: "   -42"
    输出: -42
    解释: 第一个非空白字符为 '-', 它是一个负号。
         我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
    示例 3:
    
    输入: "4193 with words"
    输出: 4193
    解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
    示例 4:
    
    输入: "words and 987"
    输出: 0
    解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
         因此无法执行有效的转换。
    示例 5:
    
    输入: "-91283472332"
    输出: -2147483648
    解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 
         因此返回 INT_MIN (−231) 。Copy to clipboardErrorCopied

### 解法 ###

class Solution {
        
        public int strToInt(String str) {
        
            if (str == null || str.length() == 0) {
        
                return 0;
            }
            // 第一个for循环是把符合要求的整数构造出来并存倒StringBuilder里
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < str.length(); i++) {
        
                char c = str.charAt(i);
                if (c == ' ' && sb.length() == 0) {
        
                    continue;
                } else if ((c == '+' || c == '-') && sb.length() == 0) {
        
                    sb.append(c);
                } else if (c >= 48 && c <= 57) {
        
                    sb.append(c);
                } else {
        
                    break;
                }
            }
            // 当字符串构造不出来符合条件的整数时直接返回0
            if (sb.length() == 0) {
        
                return 0;
            }
            // 下面的逻辑就是要把字符串例如"12345" 转换为整数 12345
            int result = 0;
            boolean flag = true;
            int i = 0;
            if (sb.charAt(0) == '+') {
        
                flag = true;
                i = 1;
            }
            else if (sb.charAt(0) == '-') {
        
                flag = false;
                i = 1;
            }
            while (i < sb.length()) {
        
                int temp = sb.charAt(i) - '0';
                // 这两个判断非常重要，如果溢出就直接返回
                if(flag == true && (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && temp > 7))){
        
                    return Integer.MAX_VALUE;
                }
                else if (flag == false && (result > Math.abs(Integer.MIN_VALUE / 10) || (-result == Integer.MIN_VALUE / 10 && temp > 8))){
        
                    return Integer.MIN_VALUE;
                }
                result = result * 10 + temp;
                i++;
            }
            // 最终结果
            if(flag == true) {
        
                return result;
            }
            else {
        
                return -result;
            }
        }
    }

[242.]: https://leetcode-cn.com/problems/valid-anagram/
[409.]: https://leetcode-cn.com/problems/longest-palindrome/
[205.]: https://leetcode-cn.com/problems/isomorphic-strings/
[647.]: https://leetcode-cn.com/problems/palindromic-substrings/
[9.]: https://leetcode-cn.com/problems/palindrome-number/
[696.]: https://leetcode-cn.com/problems/count-binary-substrings/
[Offer 58 - I.]: https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof/
[Offer 58 - II.]: https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/
[Offer 67.]: https://leetcode-cn.com/problems/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-shu-lcof/