Weitanai

# 字符串

# 1 两个字符串包含的字符是否完全相同

s = "anagram", t = "nagaram", return true.

s = "rat", t = "car", return false.

可以用 HashMap 来映射字符与出现次数，然后比较两个字符串出现的字符数量是否相同。

由于本题的字符串只包含 26 个小写字符，因此可以使用长度为 26 的整型数组对字符串出现的字符进行统计，不再使用 HashMap。

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 字符串同构

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

# 3 回文子字符串个数

1.   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++;
    }
}


private int ans = 0;
public int countSubstring(String s){
    for(int i = 0; i<s.length(); i++){
        extend(s, i, i);
        extend(s, i,i+1);
    }
    return ans;
}

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

← LinkList →