1. 字符串循环移位包含
- 1.1 题目
1
1.2 分析解答
-
法一：构建辅助字符串，利用额外空间
- 构建一个辅助字符串s = s1+s1；例如 s=s1+s1="ABCD"+"ABCD"，可以看出由s1做循环移位所得到的字符串都将是s的子串。至此问题转化成s2是否在s上的字符串问题。
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);
}
-法二：循环匹配字符串
- 循环匹配s1和s2的字符，当s1达到末尾时，返回s1首部，继续匹配。
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的每个字符都作为匹配首部进行循环匹配
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. 字符串循环移位
- 2.1 题目
2
- 2.2 分析解答
- 法一：用k将字符串隔开，然后左右部分翻转，再将整体翻转
- 将子串 s[0:str.length() - k)] 翻转，子串s[str.length() - k,str.length()] 翻转。然后将整个字符翻转可以到最终结果。
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. 字符串中单词的翻转
- 3.1 题目
3
- 3.2 分析解答
- 法一：用字符串本身的split()方法
- 直接用+号拼接字符串的性能比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();
}
}
性能更好的解答，因为正则匹配损耗性能。\s匹配任意空字符，+表示匹配多个
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; // 遇到空单词则跳过
res.append(strs[i] + " "); // 将单词拼接至 StringBuilder
}
return res.toString().trim(); // 转化为字符串，删除尾部空格，并返回
}
}
- 法二：双指针
- 倒序遍历字符串 ss ，记录单词左右索引边界 ii , jj ；
- 每确定一个单词的边界，则将其添加至单词列表 resres ；
- 最终，将单词列表拼接为字符串，并返回即可。
- 时间复杂度 O(N)O(N) ： 其中 NN 为字符串 ss 的长度，线性遍历字符串。
- 空间复杂度 O(N)O(N) ： 新建的 list(Python) 或 StringBuilder(Java) 中的字符串总长度 \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--; // 搜索首个空格
res.append(s.substring(i + 1, j + 1) + " "); // 添加单词
while(i >= 0 && s.charAt(i) == ' ') i--; // 跳过单词间空格
j = i; // j 指向下个单词的尾字符
}
return res.toString().trim(); // 转化为字符串并返回
}
}
4. 两个字符串包含的字符是否完全相同
- Valid Anagram (Easy)
- 4.1 题目
4
-
4.2分析解答
- 可以用 HashMap 来映射字符与出现次数，然后比较两个字符串出现的字符数量是否相同。
- 由于本题的字符串只包含 26 个小写字符，因此可以使用长度为 26 的整型数组对字符串出现的字符进行统计，不再使用 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. 计算一组字符集合可以组成的回文字符串的最大长度
- Longest Palindrome (Easy)
- 5.1 题目
5
-
5.2 分析解答
- 使用长度为 52 的整型数组来统计每个字符出现的个数，每个字符有偶数个可以用来构成回文字符串。
- 因为回文字符串最中间的那个字符可以单独出现，所以如果有单独的字符就把它放到最中间。
- 26个大小写字母的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++; // 这个条件下 s 中一定有单个未使用的字符存在，可以把这个字符放到回文的最中间
}
return palindrome;
}
- 使用HashMap用与存储字符出现的次数，性能比数组差
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. 字符串同构
- Isomorphic Strings (Easy)
- 6.1 题目
6
-
6.2分析解答
- 记录一个字符上次出现的位置，如果两个字符串中的字符上次出现的位置一样，那么就属于同构。
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. 回文子字符串个数
- Palindromic Substrings (Medium)
- 7.1 题目
7
7.2 分析解答
-
法一：动态规划解答
- 状态：dp[i][j] 表示字符串s在[i,j]区间的子串是否是一个回文串。
- 状态转移方程：当 s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1]) 时，dp[i][j]=true，否则为false
- 这个状态转移方程是什么意思呢？
- 当只有一个字符时，比如a自然是一个回文串。
- 当有两个字符时，如果是相等的，比如aa，也是一个回文串。
- 当有三个及以上字符时，比如ababa这个字符记作串1，把两边的a去掉，也就是bab记作串2，可以看出只要串2是一个回文串，那么左右各多了一个a的串1必定也是回文串。所以当s[i]==s[j]时，自然要看dp[i+1][j-1]是不是一个回文串。
- 时间复杂度为O(N2)，空间复杂度为O(N2)。
class Solution {
public int countSubstrings(String s) {
// 动态规划法
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;
}
}
- 法二：中心扩展法
- 回文字符串关于中心对称，这个中心既可以是一个字符（比如子串的长度为奇数时），也可以是两个字符的中间（比如子串的长度为偶数时）。那么对于长度为n的字符串，其子串的中心一共有n+（n-1）个，n个是字母，n-1个是两个字母的间歇。
- 需要找到每一个可能的对称中心有能向外扩展出多少个回文子串。要想办法表示每一个回文中心，外扩的方式都一样。
- 回文中心与子串的奇偶性有关，想必要分情况讨论。
- 如果子串的长度为奇数(形似aba)，那么第一个子串只有一个字符，其左边界left与右边界right相等。
- 如果子串的长度为偶数(形式ab，此时中心是字母的间隙)，那么第一个子串有两个字符，其左边界left与右边界right的关系为right = left + 1。
- 所以可以通过奇偶性来控制初始时left与right的关系。
- 回文中心与子串的奇偶性有关，想必要分情况讨论。
- 循环 for (int i = 0; i < chars.length * 2 - 1; i++)，i表示每一个可能的回文中心，通过i的奇偶性来设置初始的left, right。内循环进行外扩，首先保证索引不超过数组边界，其次当前判断的两个字符相等。否则,当前[left, right]不是回文子串，向外扩的也不可能是。外扩的方式就是使left--, right++。
- 时间复杂度为O(n+k)，其中k为符合条件的子串的数目。空间复杂度为O(1)。
public int countSubstrings3(String s) {
char[] chars = s.toCharArray();
int result = 0;
for (int i = 0; i < chars.length * 2 - 1; i++) { // 对每个可能的回文中心进行循环
int left = i / 2; // 当中心是两个字母的间歇时i%2 = 1；当中心是字母时 left==right都落在该字母的位置
int right = left + i % 2;
while(left >= 0 && right < chars.length && chars[left] == chars[right]){
left--;
right++;
result++;
}
}
return result;
}
8. 判断一个证书是否是回文数
- Palindrome Number (Easy)
- 8.1 题目
8
要求不能使用额外空间，也就不能将整数转换为字符串进行判断。
-
8.2 分析解答
- 将整数分成左右两部分，右边那部分需要转置，然后判断这两部分是否相等。
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;
}
}
- 暴力解，转换为字符串
class Solution {
public boolean isPalindrome(int x) {
String reversedStr = (new StringBuilder(x + "")).reverse().toString();
return (x + "").equals(reversedStr);
}
}
9. 统计二进制字符串中连续1和连续0数量相同的字符串个数
- Count Binary Substrings (Easy)
- 9.1 题目
9
-
9.2 分析解答
- 用两个长度来记录遍历过程中先遍历的长度和数字变化后的遍历长度，只要前遍历的长度比后遍历的长度更大就可以组成结果。
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;
}
