字符串循环移位包含

编程之美3.1

题目描述

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

例：

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

题目解答

s1进行循环移位的结果就是s1+s1，只需判断s2是否是s1+s1的子串即可

字符串循环移位

编程之美2.17

题目描述

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

例子：

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

题目解答

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

直接移动不就好了.

字符串中单词的翻转

程序员代码面试指南

题目描述

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

题目解答

将每个单词翻转，再将整个字符串翻转

有效的字母异位词

力扣地址

题目描述

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

示例 1:

1
2
输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

1
2
输入: s = "rat", t = "car"
输出: false

说明:
你可以假设字符串只包含小写字母。

进阶:
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

题目解答

只需判断两个字符串中每个字母出现的次数是否相同

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        a = [0] * 26
        if len(s) != len(t):
            return False
        for i in s:
            a[ord(i) - ord('a')] += 1
        for i in t:
            a[ord(i) - ord('a')] -= 1
        for i in a:
            if i != 0:
                return False
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
}

最长回文串

力扣地址

题目描述

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

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

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

示例 1:

1
2
3
4
5
6
7
8
输入:
"abccccdd"

输出:
7

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

题目解答

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def longestPalindrome(self, s: str) -> int:
        list = [0] * 100
        for i in s:
            list[ord(i) - ord('A')] += 1
        rlt = 0
        for i in list:
            rlt += i // 2 * 2
        if rlt < len(s):
            rlt += 1
        return rlt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
}

同构字符串

力扣地址

题目描述

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

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

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

示例 1:

1
2
输入: s = "egg", t = "add"
输出: true

示例 2:

1
2
输入: s = "foo", t = "bar"
输出: false

示例 3:

1
2
输入: s = "paper", t = "title"
输出: true

说明:
你可以假设 s 和 t 具有相同的长度。

题目解答

1
2
3
4
5
6
class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        for i in range(len(s)):
            if s.index(s[i]) != t.index(t[i]):
                return False
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean isIsomorphic(String s, String t) {
    int[] preIndexOfS = new int[256];
    int[] preIndexOfT = new int[256];
    for (int i = 0; i < s.length(); i++) {
        char sc = s.charAt(i), tc = t.charAt(i);
        if (preIndexOfS[sc] != preIndexOfT[tc]) {
            return false;
        }
        preIndexOfS[sc] = i + 1;
        preIndexOfT[tc] = i + 1;
    }
    return true;
}

回文子串

力扣地址

题目描述

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

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

示例 1：

1
2
3
输入："abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

1
2
3
输入："aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：

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

题目解答

中心扩展法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def countSubstrings(self, s: str) -> int:
        rlt = 0
        for i in range(len(s)):
            rlt += self.expandFromMid(s, i, i)  # 偶数情况
        for i in range(len(s)):
            rlt += self.expandFromMid(s, i, i + 1) #奇数情况
        return rlt

    def expandFromMid(self, s: str, i: int, j: int):
        count = 0
        while i >= 0 and j < len(s) and s[i] == s[j]:
            i -= 1
            j += 1
            count += 1
        return count
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private int cnt = 0;

public int countSubstrings(String s) {
    for (int i = 0; i < s.length(); i++) {
        extendSubstrings(s, i, i);     // 奇数长度
        extendSubstrings(s, i, i + 1); // 偶数长度
    }
    return cnt;
}

private void extendSubstrings(String s, int start, int end) {
    while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
        start--;
        end++;
        cnt++;
    }
}

回文数

力扣地址

题目描述

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

示例 1:

1
2
输入: 121
输出: true

示例 2:

1
2
3
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3:

1
2
3
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
1
2
3
4
5
6
7
class Solution:
    def isPalindrome(self, x: int) -> bool:
        x_str = str(x)
        x_str_r = ''.join(reversed(x_str))
        if x_str_r == x_str:
            return True
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 :

1
2
3
4
5
6
7
输入: "00110011"
输出: 6
解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。

请注意，一些重复出现的子串要计算它们出现的次数。

另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。

示例 2 :

1
2
3
输入: "10101"
输出: 4
解释: 有4个子串：“10”，“01”，“10”，“01”，它们具有相同数量的连续1和0。

注意：

  • s.length 在1到50,000之间。
  • s 只包含“0”或“1”字符。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:

    def countBinarySubstrings(self, s: str) -> int:  #00110011
        seq0, seq1 = 0, 1
        res = 0
        for i in range(1, len(s)):
            if s[i] == s[i - 1]:
                seq1 += 1
            else:
                res += min(seq0, seq1)
                seq0 = seq1
                seq1 = 1
        res += min(seq0, seq1)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
}