LeetCode题解——字符串

r囧r小猫 2023-02-19 06:27 88阅读 0赞

### 文章目录 ###

*   *  有效的字母异位词
     *   *  解法
     *  最长回文串
     *   *  解法
     *  同构字符串
     *   *  解法
     *  回文子串
     *   *  解法
     *  回文数
     *   *  解法
     *  计数二进制子串
     *   *  解法
         *   *  推荐阅读

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

给定两个字符串 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) {
        
            int[] map = new int[26];
            for (char c : s.toCharArray()) {
        
                map[c - 'a']++;
            }
            for (char c : t.toCharArray()) {
        
                map[c - 'a']--;
            }
            for (int value : map) {
        
                if (value != 0) {
        
                    return false;
                }
            }
            return true;
        }
    }

## 最长回文串 ##

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

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

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

示例 1:

输入:  
“abccccdd”

输出:  
7

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

### 解法 ###

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

## 同构字符串 ##

给定两个字符串 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;
        }
    }

## 回文子串 ##

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

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

示例 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++;
            }
        }
    }

## 回文数 ##

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

示例 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;
        }
    }

## 计数二进制子串 ##

给定一个字符串 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;
        }
    }

--------------------

#### 推荐阅读 ####

*  [机器学习资料汇总][Link 1]
 *  [吴恩达《机器学习》视频、作业、源码][Link 2]
 *  [106页《Python进阶》中文版正式发布][106_Python]
 *  [李航《统计学习方法》第二版完整课件][Link 3]
 *  [机器学习数学全书，1900页PDF下载][1900_PDF]

--------------------

![format_png][]

[Link 1]: https://mp.weixin.qq.com/s/3nOkk_Yt9D7Qp1WaWEjyZQ
[Link 2]: https://mp.weixin.qq.com/s/dErZNtBYbVA7ItPm7T_HIw
[106_Python]: https://mp.weixin.qq.com/s/_WEuuxj-QgihijjLz7NJ9g
[Link 3]: https://mp.weixin.qq.com/s/xah47OWuu8ahAUa1aFFo4Q
[1900_PDF]: https://mp.weixin.qq.com/s/9BuyhdwuHiHH3ksVUe44ZQ
[format_png]: https://imgconvert.csdnimg.cn/aHR0cDovL3dhcmRzZXB0ZW1iZXIuY2x1Yi9Gc2lzMkxhbzF6UkEtUnBic1RFREEwX3owNHdi?x-oss-process=image/format,png