字符串

1. 字符串循環(huán)移位包含

  • 1.1 題目
1

  • 1.2 分析解答

  • 法一：構(gòu)建輔助字符串，利用額外空間

    • 構(gòu)建一個(gè)輔助字符串s = s1+s1；例如 s=s1+s1="ABCD"+"ABCD"，可以看出由s1做循環(huán)移位所得到的字符串都將是s的子串。至此問(wèn)題轉(zhuǎn)化成s2是否在s上的字符串問(wèn)題。
public boolean rotateContains(String s1,String s2){
    if(s1 == null || s2 == null || s1.length()  <  s2.length())
        return false;
    StringBuilder sb = new StringBuilder(s1);
    sb.append(s1);
    return sb.toString().contains(s2);
}

-法二：循環(huán)匹配字符串

  • 循環(huán)匹配s1和s2的字符，當(dāng)s1達(dá)到末尾時(shí)，返回s1首部，繼續(xù)匹配。
public boolean rotateContains(String s1,String s2){
    if(s1 == null || s2 == null || s1.length()  <  s2.length())
        return false;
    for(int i = 0; i < s1.length(); i++){//以s1的每個(gè)字符都作為匹配首部進(jìn)行循環(huán)匹配
        int j=0;
        for(;j<s2.length();j++){
            if(s2.charAt(j) != s1.charAt((i+j)%s1.length()))
                break;
            }
            if(j == s2.length())
                return true;
    }
    return false;
}

2. 字符串循環(huán)移位

  • 2.1 題目
2
  • 2.2 分析解答
  • 法一：用k將字符串隔開(kāi)，然后左右部分翻轉(zhuǎn)，再將整體翻轉(zhuǎn)
    • 將子串 s[0:str.length() - k)] 翻轉(zhuǎn)，子串s[str.length() - k,str.length()] 翻轉(zhuǎn)。然后將整個(gè)字符翻轉(zhuǎn)可以到最終結(jié)果。
class Solution {
    public String reverseString(String str1) {
        char[] chs = str1.toCharArray();
        for(int i =0,j = str1.length()-1;i<j;i++,j--){
            char tmp = chs[i];
            chs[i] = chs[j];
            chs[j] = tmp;
        }
        return new String(chs);
    }
    public String turnRight(String str,int k){
        String substr1 = reverseString(str.substring(0,str.length() - k));
        String substr2 = reverseString(str.substring(str.length() - k,str.length()));
        return reverseString(substr1+substr2);
    }
 }
  • 法二：生成新 ss = s+s，取ss[str.length() - k, str.length() - k + str.length()]
class Solution {
    public String turnright(String str,int k){
        String ss = str+str;
        return ss.substring(str.length()-k,str.length()-k+str.length());
    }
 }

3. 字符串中單詞的翻轉(zhuǎn)

  • 3.1 題目
3
  • 3.2 分析解答
  • 法一：用字符串本身的split()方法
    • 直接用+號(hào)拼接字符串的性能比StringBuilder容器拼接字符串的性能低
class Solution {
    public String reverseWords(String s) {
        String[] strs = s.trim().split("\\s+");
        StringBuilder res = new StringBuilder();
        for(int i = strs.length - 1; i > -1; i--){
            res.append(strs[i] + " ");
        }
        return res.toString().trim();
    }
}

性能更好的解答，因?yàn)檎齽t匹配損耗性能。\s匹配任意空字符，+表示匹配多個(gè)

class Solution {
    public String reverseWords(String s) {
        String[] strs = s.trim().split(" "); // 刪除首尾空格，分割字符串
        StringBuilder res = new StringBuilder();
        for(int i = strs.length - 1; i >= 0; i--) { // 倒序遍歷單詞列表
            if(strs[i].equals("")) continue; // 遇到空單詞則跳過(guò)
            res.append(strs[i] + " "); // 將單詞拼接至 StringBuilder
        }
        return res.toString().trim(); // 轉(zhuǎn)化為字符串，刪除尾部空格，并返回
    }
}
  • 法二：雙指針
    • 倒序遍歷字符串 ss ，記錄單詞左右索引邊界 ii , jj ；
    • 每確定一個(gè)單詞的邊界，則將其添加至單詞列表 resres ；
    • 最終，將單詞列表拼接為字符串，并返回即可。
    • 時(shí)間復(fù)雜度 O(N)O(N) ： 其中 NN 為字符串 ss 的長(zhǎng)度，線(xiàn)性遍歷字符串。
    • 空間復(fù)雜度 O(N)O(N) ： 新建的 list(Python) 或 StringBuilder(Java) 中的字符串總長(zhǎng)度 \leq N≤N ，占用 O(N)O(N) 大小的額外空間。
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--; // 搜索首個(gè)空格
            res.append(s.substring(i + 1, j + 1) + " "); // 添加單詞
            while(i >= 0 && s.charAt(i) == ' ') i--; // 跳過(guò)單詞間空格
            j = i; // j 指向下個(gè)單詞的尾字符
        }
        return res.toString().trim(); // 轉(zhuǎn)化為字符串并返回
    }
}

4. 兩個(gè)字符串包含的字符是否完全相同

  1. Valid Anagram (Easy)
  • 4.1 題目
4

  • 4.2分析解答

    • 可以用 HashMap 來(lái)映射字符與出現(xiàn)次數(shù)，然后比較兩個(gè)字符串出現(xiàn)的字符數(shù)量是否相同。
    • 由于本題的字符串只包含 26 個(gè)小寫(xiě)字符，因此可以使用長(zhǎng)度為 26 的整型數(shù)組對(duì)字符串出現(xiàn)的字符進(jìn)行統(tǒng)計(jì)，不再使用 HashMap。
class Solution {
    public boolean isAnagram(String s, String t) {
        int[] ref = new int[26];
        for(char c : s.toCharArray()){
            ref[c-'a']++;
        }
        for(char c : t.toCharArray()){
            ref[c - 'a']--;
        }
        for(int count : ref){
            if(count != 0) return false;
        }
        return true;
    }
}

5. 計(jì)算一組字符集合可以組成的回文字符串的最大長(zhǎng)度

  1. Longest Palindrome (Easy)
  • 5.1 題目
5
  • 5.2 分析解答
    • 使用長(zhǎng)度為 52 的整型數(shù)組來(lái)統(tǒng)計(jì)每個(gè)字符出現(xiàn)的個(gè)數(shù)，每個(gè)字符有偶數(shù)個(gè)可以用來(lái)構(gòu)成回文字符串。
    • 因?yàn)榛匚淖址钪虚g的那個(gè)字符可以單獨(dú)出現(xiàn)，所以如果有單獨(dú)的字符就把它放到最中間。
    • 26個(gè)大小寫(xiě)字母的ASCII值，A-Z：65-90；a-z：97-122
public int longestPalindrome(String s) {
    int[] cnts = new int[58];
    for (char c : s.toCharArray()) {
        cnts[c]++;
    }
    int palindrome = 0;
    for (int cnt : cnts) {
        palindrome += (cnt / 2) * 2;
    }
    if (palindrome < s.length()) {
        palindrome++;   // 這個(gè)條件下 s 中一定有單個(gè)未使用的字符存在，可以把這個(gè)字符放到回文的最中間
    }
    return palindrome;
}
  • 使用HashMap用與存儲(chǔ)字符出現(xiàn)的次數(shù)，性能比數(shù)組差
class Solution {
    public int longestPalindrome(String s) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for(char c : s.toCharArray()){
            map.put(c - 'A', map.getOrDefault(c - 'A', 0) + 1);
        }
        int res = 0;
        for(int value : map.values()){
            res += value / 2 * 2;
        }
        if(res < s.length()){
            res += 1;
        }
        return res;
    }
}

6. 字符串同構(gòu)

  1. Isomorphic Strings (Easy)
  • 6.1 題目
6
  • 6.2分析解答
    • 記錄一個(gè)字符上次出現(xiàn)的位置，如果兩個(gè)字符串中的字符上次出現(xiàn)的位置一樣，那么就屬于同構(gòu)。
class Solution {
    public boolean isIsomorphic(String s, String t) {
        int[] preIndexOfS = new int[128];
        int[] preIndexOfT = new int[128];
        for(int i = 0; i < s.length(); i++){
            char sc = s.charAt(i), tc = t.charAt(i);
            if(preIndexS[sc] != preIndexT[tc])
                return false;
            preIndexS[sc] = i + 1;
            preIndexT[tc] = i + 1;
        }
        return true;
    }
}

7. 回文子字符串個(gè)數(shù)

  1. Palindromic Substrings (Medium)
  • 7.1 題目
7

  • 7.2 分析解答

  • 法一：動(dòng)態(tài)規(guī)劃解答

    • 狀態(tài)：dp[i][j] 表示字符串s在[i,j]區(qū)間的子串是否是一個(gè)回文串。
    • 狀態(tài)轉(zhuǎn)移方程：當(dāng) s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1]) 時(shí)，dp[i][j]=true，否則為false
    • 這個(gè)狀態(tài)轉(zhuǎn)移方程是什么意思呢？
      • 當(dāng)只有一個(gè)字符時(shí)，比如a自然是一個(gè)回文串。
      • 當(dāng)有兩個(gè)字符時(shí)，如果是相等的，比如aa，也是一個(gè)回文串。
      • 當(dāng)有三個(gè)及以上字符時(shí)，比如ababa這個(gè)字符記作串1，把兩邊的a去掉，也就是bab記作串2，可以看出只要串2是一個(gè)回文串，那么左右各多了一個(gè)a的串1必定也是回文串。所以當(dāng)s[i]==s[j]時(shí)，自然要看dp[i+1][j-1]是不是一個(gè)回文串。
    • 時(shí)間復(fù)雜度為O(N2)，空間復(fù)雜度為O(N2)。
class Solution {
    public int countSubstrings(String s) {
        // 動(dòng)態(tài)規(guī)劃法
        boolean[][] dp = new boolean[s.length()][s.length()];
        int ans = 0;

        for (int j = 0; j < s.length(); j++) {
            for (int i = 0; i <= j; i++) {
                if (s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    ans++;
                }
            }
        }

        return ans;
    }
}
  • 法二：中心擴(kuò)展法
    • 回文字符串關(guān)于中心對(duì)稱(chēng)，這個(gè)中心既可以是一個(gè)字符（比如子串的長(zhǎng)度為奇數(shù)時(shí)），也可以是兩個(gè)字符的中間（比如子串的長(zhǎng)度為偶數(shù)時(shí)）。那么對(duì)于長(zhǎng)度為n的字符串，其子串的中心一共有n+（n-1）個(gè)，n個(gè)是字母，n-1個(gè)是兩個(gè)字母的間歇。
    • 需要找到每一個(gè)可能的對(duì)稱(chēng)中心有能向外擴(kuò)展出多少個(gè)回文子串。要想辦法表示每一個(gè)回文中心，外擴(kuò)的方式都一樣。
      • 回文中心與子串的奇偶性有關(guān)，想必要分情況討論。
        • 如果子串的長(zhǎng)度為奇數(shù)(形似aba)，那么第一個(gè)子串只有一個(gè)字符，其左邊界left與右邊界right相等。
        • 如果子串的長(zhǎng)度為偶數(shù)(形式ab，此時(shí)中心是字母的間隙)，那么第一個(gè)子串有兩個(gè)字符，其左邊界left與右邊界right的關(guān)系為right = left + 1。
        • 所以可以通過(guò)奇偶性來(lái)控制初始時(shí)left與right的關(guān)系。
    • 循環(huán) for (int i = 0; i < chars.length * 2 - 1; i++)，i表示每一個(gè)可能的回文中心，通過(guò)i的奇偶性來(lái)設(shè)置初始的left, right。內(nèi)循環(huán)進(jìn)行外擴(kuò)，首先保證索引不超過(guò)數(shù)組邊界，其次當(dāng)前判斷的兩個(gè)字符相等。否則,當(dāng)前[left, right]不是回文子串，向外擴(kuò)的也不可能是。外擴(kuò)的方式就是使left--, right++。
    • 時(shí)間復(fù)雜度為O(n+k)，其中k為符合條件的子串的數(shù)目。空間復(fù)雜度為O(1)。
public int countSubstrings3(String s) {
        char[] chars = s.toCharArray();
        int result = 0;
        for (int i = 0; i < chars.length * 2 - 1; i++) { // 對(duì)每個(gè)可能的回文中心進(jìn)行循環(huán)
            int left = i / 2; // 當(dāng)中心是兩個(gè)字母的間歇時(shí)i%2 = 1；當(dāng)中心是字母時(shí) left==right都落在該字母的位置
            int right = left + i % 2;
            while(left >= 0 && right < chars.length && chars[left] == chars[right]){
                left--;
                right++;
                result++;
            }
        }
        return result;
    }

8. 判斷一個(gè)證書(shū)是否是回文數(shù)

  1. Palindrome Number (Easy)
  • 8.1 題目
8

要求不能使用額外空間，也就不能將整數(shù)轉(zhuǎn)換為字符串進(jìn)行判斷。

  • 8.2 分析解答
    • 將整數(shù)分成左右兩部分，右邊那部分需要轉(zhuǎn)置，然后判斷這兩部分是否相等。
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;

    }
}
  • 暴力解，轉(zhuǎn)換為字符串
class Solution {
    public boolean isPalindrome(int x) {
        String reversedStr = (new StringBuilder(x + "")).reverse().toString();
        return (x + "").equals(reversedStr);
    }
}

9. 統(tǒng)計(jì)二進(jìn)制字符串中連續(xù)1和連續(xù)0數(shù)量相同的字符串個(gè)數(shù)

  1. Count Binary Substrings (Easy)
  • 9.1 題目
9
  • 9.2 分析解答
    • 用兩個(gè)長(zhǎng)度來(lái)記錄遍歷過(guò)程中先遍歷的長(zhǎng)度和數(shù)字變化后的遍歷長(zhǎng)度，只要前遍歷的長(zhǎng)度比后遍歷的長(zhǎng)度更大就可以組成結(jié)果。
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;
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容