LeetCode-字符串专题

1.有效的字母异位词

valid-anagram(easy)
Leetcode

解法1：用hashmap把每个出现过的字符极其数量记录下来

class SolutionOne {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        HashMap<Character, Integer> sMap = new HashMap();
        char[] ArrayS = s.toCharArray();
        char[] ArrayT = t.toCharArray();
        for (int i = 0; i < ArrayS.length; i++) {
            if (sMap.containsKey(ArrayS[i])) {
                sMap.put(ArrayS[i], sMap.get(ArrayS[i]) + 1);
            } else {
                sMap.put(ArrayS[i], 1);
            }
        }
        for (int i = 0; i < ArrayT.length; i++) {
            if (sMap.containsKey(ArrayT[i])) {
                if (sMap.get(ArrayT[i]) >= 1) {
                    sMap.put(ArrayT[i], sMap.get(ArrayT[i]) - 1);
                }

            } else {
                return false;
            }
        }
        int count = 0;
        for (Character key : sMap.keySet()) {
            count += sMap.get(key);
        }
        if (count == 0) {
            return true;
        }
        return false;

    }
}

解法2：利用数组，将出现过的字符记录下来

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;
    }
}

2.最长回文字符串

longest-palindrome(easy)
Leetcode

count += (map.get(c) / 2) * 2
这一步是比较关键的，有一些字母虽然是奇数个数，但是-1之后是可以算到字符串数量中的。

解法1：用hashmap把每个出现过的字符的数量记录下来

//2020年11月2日
class Solution {
        public int longestPalindrome(String s) {
        char[] arr = s.toCharArray();
        HashMap<Character,Integer> map = new HashMap();
        for(char c : arr){
            if(map.containsKey(c)){
                map.put(c,map.get(c)+1);
            }else{
                map.put(c,1);
            }
        }
        int count = 0;
        for(char c : map.keySet()){
            count += (map.get(c) / 2) * 2;
        }
        if(count < s.length()){
            count++;
        }
        return count;
    }
}

解法2：利用数组，将出现过的字符记录下来

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;
}
}

3.同构字符串

isomorphic-strings(easy)
Leetcode

思路：
记录下初始的字符对应关系，当随着i的增大，一旦有字符对应的关系与原来的关系不一样，就返回false

//2020年11月2日
class Solution {
    public boolean isIsomorphic(String s, String t) {
        int[] arrs = new int[256];
        int[] arrt = new int[256];
        char[] sArr = s.toCharArray();
        char[] tArr = t.toCharArray();
        for(int i=0;i<s.length();i++){
            if(arrs[sArr[i]] != arrt[tArr[i]]){
                return false;
            }
            arrs[sArr[i]] = i+20;
            arrt[tArr[i]] = i+20;
        }
        return true;
    }
}

4.回文字符串个数

Palindromic Substrings (Medium)
Leetcode

解法1：
暴力解法，双重循环遍历当前字符数组，每遇到一个可行的字符串就去判断是否是回文字符串，是的话count++
此解法时间复杂度为O(N^3),外部两层循环加内部一层循环，很耗时间
图片说明

//2020年11月4日
public int countSubstrings(String s) {
        char[] c = s.toCharArray();
        int count = 0;
        for(int i=0;i<c.length;i++){
            for(int j=i;j<c.length;j++){
                if(isIsomorphic(c,i,j)){
                    count++;
                }
            }
        }
        return count;
    }
    public static boolean isIsomorphic(char[] arr,int start,int end){
        int length = end - start + 1;
        for (int i = 0; i <= (end-start) / 2; i++) {
            if (arr[start+i] != arr[end - i]) {
                return false;
            }
        }
        return true;
    }

解法2：动态规划
这里先挖个坑，周末把视频看了再补上

const countSubstrings = (s) => {
  let count = 0;
  const len = s.length;

  const dp = new Array(len);
  for (let i = 0; i < len; i++) {
    dp[i] = new Array(len).fill(false);
  }

  for (let j = 0; j < len; j++) {
    for (let i = 0; i <= j; i++) {
      if (i == j) { // 单个字符
        dp[i][j] = true;
        count++;
      } else if (j - i == 1 && s[i] == s[j]) { // 两个字符 
        dp[i][j] = true;
        count++;
      } else if (j - i > 1 && s[i] == s[j] && dp[i + 1][j - 1]) { // 多于两个字符
        dp[i][j] = true;
        count++;
      }
    }
  }
  return count;
};

作者：xiao_ben_zhu
链接：https://leetcode-cn.com/problems/palindromic-substrings/solution/shou-hua-tu-jie-dong-tai-gui-hua-si-lu-by-hyj8/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

5.回文数

Palindrome Number (Easy)
Leetcode

解法1：
转换成字符串解
图片说明

//2020年11月5日
class Solution {
    public boolean isPalindrome(int x) {
        if(x < 0) return false;
        String s = String.valueOf(x);
        for(int i=0;i<s.length()/2;i++){
            if(s.charAt(i)!=s.charAt(s.length()-1-i)){
                return false;
            }
        }
        return true;
    }
}

解法2：
数学法：利用除法和取余，拿到第一位和最后一位数，进行比较，相等则进行下次的比较
图片说明

class Solution {
    public boolean isPalindrome(int x) {
        //边界判断
        if (x < 0) return false;
        int div = 1;
        //
        while (x / div >= 10) div *= 10;
        while (x > 0) {
            int left = x / div;
            int right = x % 10;
            if (left != right) return false;
            x = (x % div) / 10;
            div /= 100;
        }
        return true;
    }
}

6.计数二进制子串

Count Binary Substrings (Easy)
Leetcode

解法1：
将字符串 s 按照 0 和 1 的连续段分组，存在数组中。
两段数字一定是不一样的，要么是1110000[3,4]，要么是000111[3,3].
二进制字串由两个数中少的那个决定

//2020年11月5日
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;
}