LeetCode 字符串(一) - LeetCode-242、409

发表于 | 分类于 |

1. 字符串循环移位包含

编程之美 3.1

1
2
s1 = AABCD, s2 = CDAA
Return : true

给定两个字符串 s1 和 s2，要求判定 s2 是否能够被 s1 做循环移位得到的字符串包含。

s1 进行循环移位的结果是 s1s1 的子字符串，因此只要判断 s2 是否是 s1s1 的子字符串即可。

2. 字符串循环移位

编程之美 2.17

1
2
s = "abcd123" k = 3
Return "123abcd"

将字符串向右循环移动 k 位。

将 abcd123 中的 abcd 和 123 单独翻转，得到 dcba321，然后对整个字符串进行翻转，得到 123abcd。

3. 字符串中单词的翻转

程序员代码面试指南

1
2
s = "I am a student"
Return "student a am I"

将每个单词翻转，然后将整个字符串翻转。

242. 两个字符串包含的字符是否完全相同

242.Valid Anagram (Easy)

Leetcode / 力扣

2020-7-18 16:17:33

题目描述

1
2
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.

可以用 HashMap 来映射字符与出现次数，然后比较两个字符串出现的字符数量是否相同。

由于本题的字符串只包含 26 个小写字符，因此可以使用长度为 26 的整型数组对字符串出现的字符进行统计，不再使用 HashMap。

解题思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean isAnagram(String s, String t) {
        int[] cnts = new int[26];
        for(char c : s.toCharArray()){
            cnts[c - 'a'] ++;
        }
        for(char c : t.toCharArray()){
            cnts[c - 'a'] --;
        }
        for(int cnt : cnts){
            if(cnt != 0){
                return false;
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
//直接排序法
public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    char[] str1 = s.toCharArray();
    char[] str2 = t.toCharArray();
    Arrays.sort(str1);
    Arrays.sort(str2);
    return Arrays.equals(str1, str2);
}

409. 最长回文串 - 计算一组字符集合可以组成的回文字符串的最大长度

409.Longest Palindrome (Easy)

Leetcode / 力扣

2020-8-7 21:35:31

题目描述

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。在构造过程中，请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。

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

1
2
3
4
5
示例 1:

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

解题思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int longestPalindrome(String s) {
        int[] cnts = new int[256];
        for(char c : s.toCharArray()){
            cnts[c]++;
        }
        int palindrome = 0;
        for (int cnt : cnts) {
            palindrome += (cnt / 2) * 2;
        }
        if (palindrome < s.length()) {
            palindrome++;   // 这个条件下 s 中一定有单个未使用的字符存在，可以把这个字符放到回文的最中间
        }
        return palindrome;
    }
}