點選藍字加關注，人在江湖不迷路
作者：CYC2018
文章連結：https://github.com/CyC2018/CS-Notes/blob/master/docs/notes/Leetcode%20%E9%A2%98%E8%A7%A3.md
本文主要介紹的是LeetCode題庫中與字元串相關的經典題目，提供了LeetCode原題題号，參考答案，以及題目的部分解析。
大家可以參考這個刷題指南來完成對字元串部分題目的練習，當然，這隻是一部分，字元串的相關題目還有很多，譬如最長公共子序列和最長公共子串，這裡列舉的隻是LeetCode中的字元串題目。
字元串
兩個字元串包含的字元是否完全相同
242. Valid Anagram (Easy)
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false. 複制
字元串隻包含小寫字元，總共有 26 個小寫字元。可以用 HashMap 來映射字元與出現次數。因為鍵的範圍很小，是以可以使用長度為 26 的整型數組對字元串出現的字元進行統計，然後比較兩個字元串出現的字元數量是否相同。
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;} 複制
計算一組字元集合可以組成的回文字元串的最大長度
409. Longest Palindrome (Easy)
Input : "abccccdd"
Output : 7
Explanation : One longest palindrome that can be built is "dccaccd", whose length is 7. 複制
使用長度為 256 的整型數組來統計每個字元出現的個數，每個字元有偶數個可以用來構成回文字元串。
因為回文字元串最中間的那個字元可以單獨出現，是以如果有單獨的字元就把它放到最中間。
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;} 複制
字元串同構
205. Isomorphic Strings (Easy)
Given "egg", "add", return true.
Given "foo", "bar", return false.
Given "paper", "title", return true. 複制
記錄一個字元上次出現的位置，如果兩個字元串中的字元上次出現的位置一樣，那麼就屬于同構。
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;} 複制
回文子字元串
647. Palindromic Substrings (Medium)
Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa". 複制
從字元串的某一位開始，嘗試着去擴充子字元串。
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++; }} 複制
判斷一個整數是否是回文數
9. Palindrome Number (Easy)
要求不能使用額外空間，也就不能将整數轉換為字元串進行判斷。
将整數分成左右兩部分，右邊那部分需要轉置，然後判斷這兩部分是否相等。
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;} 複制
統計二進制字元串中連續 1 和連續 0 數量相同的子字元串個數
696. Count Binary Substrings (Easy)
Input: "00110011"
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". 複制
複制
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;} 複制
字元串循環移位包含
程式設計之美：3.1
s1 = AABCD, s2 = CDAA
Return : true 複制
給定兩個字元串 s1 和 s2，要求判定 s2 是否能夠被 s1 做循環移位得到的字元串包含。
s1 進行循環移位的結果是 s1s1 的子字元串，是以隻要判斷 s2 是否是 s1s1 的子字元串即可。
字元串循環移位
程式設計之美：2.17
s = "abcd123" k = 3
Return "123abcd" 複制
将字元串向右循環移動 k 位。
将 abcd123 中的 abcd 和 123 單獨逆序，得到 dcba321，然後對整個字元串進行逆序，得到 123abcd。
字元串中單詞的翻轉
程式員代碼面試指南
s = "I am a student"
return "student a am I" 複制
将每個單詞逆序，然後将整個字元串逆序