字母異位詞&贖金信&最小覆蓋子串&字符串的排列&串連所有單詞的子串

字母異位詞分組

給定一個(gè)字符串?dāng)?shù)組，將字母異位詞組合在一起。字母異位詞指字母相同，但排列不同的字符串。

示例:

輸入: ["eat", "tea", "tan", "ate", "nat", "bat"]
輸出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]

說明：

  • 所有輸入均為小寫字母。
  • 不考慮答案輸出的順序。

方法一：排序數(shù)組分類
維護(hù)一個(gè)映射，key為字符串中字符的最小字典序，value為排列不同的字符串

public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();
    for (String s : strs) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        if (!map.containsKey(String.valueOf(chars))) {
            map.put(String.valueOf(chars), new ArrayList<>());
        }
        map.get(String.valueOf(chars)).add(s);
    }
    return new ArrayList<>(map.values());
}

時(shí)間復(fù)雜度：O(NKlogK)，其中 N 是 strs 的長度，而 K 是 strs 中字符串的最大長度

方法二：按計(jì)數(shù)分類
根據(jù)每個(gè)字符串中字母出現(xiàn)的次數(shù)構(gòu)造字符串，作為key

public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();
    for (String s : strs) {
        int[] counts = new int[26];
        char[] chars = s.toCharArray();
        for (char c : chars) {
            counts[c - 'a']++;
        }
        StringBuilder sb = new StringBuilder();
        for (int count : counts) {
            sb.append("#").append(count).append("#");
        }
        String key = sb.toString();
        if (!map.containsKey(key)) {
            map.put(key, new ArrayList<>());
        }
        map.get(key).add(s);
    }
    return new ArrayList<>(map.values());
}

時(shí)間復(fù)雜度O(NK)

找到字符串中所有字母異位詞

給定一個(gè)字符串 s和一個(gè)非空字符串 p，找到 s中所有是 p的字母異位詞的子串，返回這些子串的起始索引。

字符串只包含小寫英文字母，并且字符串 s和 p的長度都不超過 20100。

說明：

  • 字母異位詞指字母相同，但排列不同的字符串。
  • 不考慮答案輸出的順序。

示例 1:

輸入:s: "cbaebabacd" p: "abc"
輸出:[0, 6]
解釋:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母異位詞。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母異位詞。

示例 2:

輸入:s: "abab" p: "ab"
輸出:[0, 1, 2]
解釋:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母異位詞。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母異位詞。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母異位詞

方法一：暴力（超時(shí)）
依次判斷s中所有長度和p的長度相同的子串和p是否是異位詞

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> ans = new ArrayList<>();
    int len = p.length();
    char[] pChars = p.toCharArray();
    Arrays.sort(pChars);
    for (int i = 0; i <= s.length() - len; i++) {
        char[] temp = new char[len];
        for (int j = 0; j < len; j++) {
            temp[j] = s.charAt(i + j);
        }
        Arrays.sort(temp);
        if (Arrays.toString(temp).equals(Arrays.toString(pChars))) {
            ans.add(i);
        }
    }
    return ans;
}

用計(jì)數(shù)法可以通過

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> res = new ArrayList<>();
    int[] pCount = new int[26];
    for (int i = 0; i < p.length(); i++) {
        pCount[p.charAt(i) - 'a']++;
    }
    for (int i = 0; i <= s.length() - p.length(); i++) {
        String subStr = s.substring(i, i + p.length());
        int[] subCount = new int[26];
        for (int j = 0; j < subStr.length(); j++) {
            subCount[subStr.charAt(j) - 'a']++;
        }
        boolean isEqual = true;
        for (int j = 0; j < 26; j++) {
            if (pCount[j] != subCount[j]) {
                isEqual = false;
                break;
            }
        }
        if (isEqual) {
            res.add(i);
        }
    }
    return res;
}

方法二：滑動(dòng)窗口
先用一個(gè)map存在p中字母存在的次數(shù)，再用一個(gè)map存滑動(dòng)窗口中字母存在的次數(shù)
滑動(dòng)窗口指針i,j，每次j向右移動(dòng)，更新j對應(yīng)字母出現(xiàn)的次數(shù)，如果比p中map的大，i指針向右移動(dòng)，直到不比map大，i在移動(dòng)過程中也要更新次數(shù)，如果窗口大小和p的長度相等，說明找到了一個(gè)滿足條件的值

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> ans = new ArrayList<>();
    int[] map = new int[26];
    for (int i = 0; i < p.length(); i++) {
        map[p.charAt(i) - 'a']++;
    }
    int i = 0, j = 0;
    int[] sMap = new int[26];
    while (j < s.length()) {
        int cur = s.charAt(j) - 'a';
        sMap[cur]++;
        j++;
        while (sMap[cur] > map[cur]) {
            sMap[s.charAt(i) - 'a']--;
            i++;
        }
        if (j - i == p.length()) {
            ans.add(i);
        } 
    }
    return ans;
}

有效的字母異位詞

給定兩個(gè)字符串 s 和 t ，編寫一個(gè)函數(shù)來判斷 t 是否是 s 的字母異位詞。

注意：若 s 和 t中每個(gè)字符出現(xiàn)的次數(shù)都相同，則稱 s 和 t互為字母異位詞。

示例 1:

輸入: s = "anagram", t = "nagaram"
輸出: true
</pre>

示例 2:

輸入: s = "rat", t = "car"
輸出: false

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    int[] smap = new int[26];
    int[] tmap = new int[26];
    for (int i = 0; i < s.length(); i++) {
        smap[s.charAt(i) - 'a']++;
    }
    for (int i = 0; i < t.length(); i++) {
        char c = t.charAt(i);
        if (smap[c - 'a'] <= tmap[c - 'a']) {
            return false;
        }
        tmap[c - 'a']++;
    }
    return true;
}

只統(tǒng)計(jì)一個(gè)字符串：

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    int[] smap = new int[26];
    for (int i = 0; i < s.length(); i++) {
        smap[s.charAt(i) - 'a']++;
    }
    for (int i = 0; i < t.length(); i++) {
        char c = t.charAt(i);
        if (smap[c - 'a'] == 0) {
            return false;
        }
        smap[c - 'a']--;
    }
    return true;
}

贖金信

給你兩個(gè)字符串：ransomNote 和 magazine ，判斷 ransomNote 能不能由 magazine 里面的字符構(gòu)成。

如果可以，返回 true ；否則返回 false 。

magazine 中的每個(gè)字符只能在 ransomNote 中使用一次。

示例 1：

輸入：ransomNote = "a", magazine = "b"
輸出：false

示例 2：

輸入：ransomNote = "aa", magazine = "ab"
輸出：false

示例 3：

輸入：ransomNote = "aa", magazine = "aab"
輸出：true

public boolean canConstruct(String ransomNote, String magazine) {
    int[] map = new int[26];
    for (int i = 0; i < ransomNote.length(); i++) {
        map[ransomNote.charAt(i) - 'a']++;
    }
    int distance = ransomNote.length();
    for (int i = 0; i < magazine.length(); i++) {
        char c = magazine.charAt(i);
        if (map[c - 'a'] > 0) {
            map[c - 'a']--;
            distance--;
        }
        if (distance == 0) {
            return true;
        }
    }
    return false;
}

最小覆蓋子串

給你一個(gè)字符串 S、一個(gè)字符串 T，請?jiān)谧址?S 里面找出：包含 T 所有字符的最小子串。

示例：

輸入: S = "ADOBECODEBANC", T = "ABC"
輸出: "BANC"

說明：

  • 如果 S 中不存這樣的子串，則返回空字符串 ""。
  • 如果 S 中存在這樣的子串，我們保證它是唯一的答案。

方法一：暴力（超時(shí)）
枚舉s所有的子串，統(tǒng)計(jì)字符的頻數(shù)看是否符合條件

public String minWindow(String s, String t) {
    String ans = "";
    int minLen = s.length();
    int[] tMap = new int[128];
    for (int i = 0; i < t.length(); i++) {
        tMap[t.charAt(i)]++;
    }
    for (int start = 0; start <= s.length() - t.length(); start++) {
        for (int end = start + t.length() - 1; end < s.length(); end++) {
            if (end - start + 1 > minLen) {//優(yōu)化，區(qū)間比找到的長度更長就不用考慮了
                break;
            }
            int[] sMap = new int[128];
            for (int i = start; i <= end; i++) {
                sMap[s.charAt(i)]++;
            }
            boolean flag = true;
            for (int i = 0; i < t.length(); i++) {
                char c = t.charAt(i);
                if (sMap[c] < tMap[c]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                ans = s.substring(start, end + 1);
                minLen = end - start + 1;
                break;//小優(yōu)化，不用往右邊找了
            }
        }
    }
    return ans;
}

時(shí)間復(fù)雜度O(s3+t)

小優(yōu)化：直接在循環(huán)中統(tǒng)計(jì)頻數(shù)

public String minWindow(String s, String t) {
    String ans = "";
    int minLen = s.length();
    int[] tMap = new int[128];
    for (int i = 0; i < t.length(); i++) {
        tMap[t.charAt(i)]++;
    }
    for (int start = 0; start <= s.length() - t.length(); start++) {
        int[] sMap = new int[128];
        int end = start + t.length() - 1;
        for (int i = start; i < end; i++) {
            sMap[s.charAt(i)]++;
        }
        for (end = start + t.length() - 1; end < s.length(); end++) {
            if (end - start + 1 > minLen) {//優(yōu)化，區(qū)間比找到的長度更長就不用考慮了
                break;
            }
            sMap[s.charAt(end)]++;              
            boolean flag = true;
            for (int i = 0; i < t.length(); i++) {
                char c = t.charAt(i);
                if (sMap[c] < tMap[c]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                ans = s.substring(start, end + 1);
                minLen = end - start + 1;
                break;//小優(yōu)化，不用往右邊找了
            }
        }
    }
    return ans;
}

方法二：滑動(dòng)窗口
滑動(dòng)窗口中的都是滿足條件的，移動(dòng)左邊界找到最小的子串

public String minWindow(String s, String t) {
    String ans = "";
    int minLen = s.length();
    int[] tMap = new int[128];
    int[] sMap = new int[128];
    for (int i = 0; i < t.length(); i++) {
        tMap[t.charAt(i)]++;
    }
    int left = 0;
    int right = 0;
    int distance = 0;//滑動(dòng)窗口中包含t中字符的個(gè)數(shù)，不重復(fù)計(jì)算
    while (right < s.length()) {
        char rightChar = s.charAt(right);
        if (tMap[rightChar] == 0) {//這個(gè)判斷其實(shí)可以刪掉
            right++;
            continue;
        }
        if (sMap[rightChar] < tMap[rightChar]) {
            distance++;
        }
        sMap[rightChar]++;
        right++;
        while (distance == t.length()) {//滑動(dòng)窗口包含了t中所有字符，移動(dòng)左邊界
            if (right - left <= minLen) {
                minLen = right - left;
                ans = s.substring(left, right);
            }
            char leftChar = s.charAt(left);
            if (tMap[leftChar] == 0) {//這個(gè)判斷其實(shí)可以刪掉
                left++;
                continue;
            }
            if (sMap[leftChar] == tMap[leftChar]) {
                distance--;
            }
            sMap[leftChar]--;
            left++;
        }
    }
    return ans;
}

時(shí)間復(fù)雜度O(s+t)：右邊界s，最壞情況下左邊界s-t

不用存s的頻數(shù)

public String minWindow(String s, String t) {
    String ans = "";
    int minLen = s.length();
    int[] tMap = new int[128];
    for (int i = 0; i < t.length(); i++) {
        tMap[t.charAt(i)]++;
    }
    int left = 0;
    int right = 0;
    int distance = t.length();//滑動(dòng)窗口中包含還差t中字符的個(gè)數(shù)
    while (right < s.length()) {
        char rightChar = s.charAt(right);
        if (tMap[rightChar] > 0) {
            distance--;
        }
        tMap[rightChar]--;
        right++;
        while (distance == 0) {//滑動(dòng)窗口包含了t中所有字符，移動(dòng)左邊界
            if (right - left <= minLen) {
                minLen = right - left;
                ans = s.substring(left, right);
            }
            char leftChar = s.charAt(left);
            if (tMap[leftChar] == 0) {
                distance++;
            }
            tMap[leftChar]++;
            left++;
        }
    }
    return ans;
}

字符串的排列

給你兩個(gè)字符串 s1 和 s2 ，寫一個(gè)函數(shù)來判斷 s2 是否包含 s1的排列。如果是，返回 true ；否則，返回 false 。

換句話說，s1 的排列之一是 s2 的 子串 。

示例 1：

輸入：s1 = "ab" s2 = "eidbaooo"
輸出：true
解釋：s2 包含 s1 的排列之一 ("ba").

示例 2：

輸入：s1= "ab" s2 = "eidboaoo"
輸出：false

相當(dāng)給你一個(gè) S 和一個(gè) T，請問你 S 中是否存在一個(gè)子串，包含 T 中所有字符且不包含其他字符？

滑動(dòng)窗口

public boolean checkInclusion(String s1, String s2) {
    if (s1.length() > s2.length()) {
        return false;
    }
    int[] map = new int[26];
    for (int i = 0; i < s1.length(); i++) {
        map[s1.charAt(i) - 'a']++;
    }
    int distance = s1.length();
    int left = 0, right = 0;
    while (right < s2.length()) {
        char c = s2.charAt(right);
        right++;
        if (map[c - 'a'] > 0) {
            distance--;
        }
        map[c - 'a']--;
        while (distance == 0) {
            if (right - left == s1.length()) {
                return true;
            }
            c = s2.charAt(left);
            if (map[c - 'a'] == 0) {
                distance++;
            }
            map[c - 'a']++;
            left++;
        }
    }
    return false;
}

串聯(lián)所有單詞的子串

給定一個(gè)字符串 s和一個(gè)字符串?dāng)?shù)組 words。 words 中所有字符串 長度相同。
s中的 串聯(lián)子串 是指一個(gè)包含 words 中所有字符串以任意順序排列連接起來的子串。

  • 例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串聯(lián)子串。 "acdbef" 不是串聯(lián)子串，因?yàn)樗皇侨魏?words 排列的連接。

返回所有串聯(lián)子串在 s中的開始索引。你可以以 任意順序 返回答案。

示例 1：

輸入：s = "barfoothefoobarman", words = ["foo","bar"]
輸出：[0,9]
解釋：因?yàn)?words.length == 2 同時(shí) words[i].length == 3，連接的子字符串的長度必須為 6。
子串 "barfoo" 開始位置是 0。它是 words 中以 ["bar","foo"] 順序排列的連接。
子串 "foobar" 開始位置是 9。它是 words 中以 ["foo","bar"] 順序排列的連接。
輸出順序無關(guān)緊要。返回 [9,0] 也是可以的。

示例 2：

輸入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
輸出：[]
解釋：因?yàn)閣ords.length == 4 并且 words[i].length == 4，所以串聯(lián)子串的長度必須為 16。
s 中沒有子串長度為 16 并且等于 words 的任何順序排列的連接。
所以我們返回一個(gè)空數(shù)組。

用哈希表統(tǒng)計(jì)

public List<Integer> findSubstring(String s, String[] words) {
    List<Integer> res = new ArrayList<>();
    int ls = s.length();
    int wordsCount = words.length;
    int wordLen = words[0].length();
    Map<String, Integer> map = new HashMap<>();
    for (String word : words) {
        map.put(word, map.getOrDefault(word, 0) + 1);
    }
    for (int i = 0; i + wordLen * wordsCount <= ls; i++) {
        Map<String, Integer> tmp = new HashMap<>();
        for (int j = 0; j < wordsCount; j++) {
            String word = s.substring(i + j * wordLen, i + (j + 1) * wordLen);
            tmp.put(word, tmp.getOrDefault(word, 0) + 1);
            if (tmp.get(word) > map.getOrDefault(word, 0)) {
                break;
            }
        }
        if (tmp.equals(map)) {
            res.add(i);
        }
    }
    return res;
}

滑動(dòng)窗口
此題是438. 找到字符串中所有字母異位詞的進(jìn)階版。不同的是第 438 題的元素是字母，而此題的元素是單詞，可以用類似的方法二的滑動(dòng)窗口來解這題。

記 words 的長度為 m，words 中每個(gè)單詞的長度為 n，s 的長度為 ls。首先需要將 s 劃分為單詞組，每個(gè)單詞的大小均為 n （首尾除外）。這樣的劃分方法有 n 種，即先刪去前 i （i=0～n?1）個(gè)字母后，將剩下的字母進(jìn)行劃分，如果末尾有不到 n 個(gè)字母也刪去。對這 n 種劃分得到的單詞數(shù)組分別使用滑動(dòng)窗口對 words 進(jìn)行類似于「字母異位詞」的搜尋。

劃分成單詞組后，一個(gè)窗口包含 s 中前 m 個(gè)單詞，用一個(gè)哈希表 differ 表示窗口中單詞頻次和 words 中單詞頻次之差。初始化 differ 時(shí)，出現(xiàn)在窗口中的單詞，每出現(xiàn)一次，相應(yīng)的值增加 1，出現(xiàn)在 words 中的單詞，每出現(xiàn)一次，相應(yīng)的值減少 1。然后將窗口右移，右側(cè)會(huì)加入一個(gè)單詞，左側(cè)會(huì)移出一個(gè)單詞，并對 differ 做相應(yīng)的更新。窗口移動(dòng)時(shí)，若出現(xiàn) differ 中值不為 0 的鍵的數(shù)量為 0，則表示這個(gè)窗口中的單詞頻次和 words 中單詞頻次相同，窗口的左端點(diǎn)是一個(gè)待求的起始位置。劃分的方法有 n 種，做 n 次滑動(dòng)窗口后，即可找到所有的起始位置。

public List<Integer> findSubstring(String s, String[] words) {
    List<Integer> res = new ArrayList<>();
    int ls = s.length();
    int wordsCount = words.length;
    int wordLen = words[0].length();
    for (int i = 0; i < wordLen && i + wordLen * wordsCount <= ls; i++) {
        Map<String, Integer> differ = new HashMap<>();
        for (int j = 0; j < wordsCount; j++) {
            String word = s.substring(i + j * wordLen, i + (j + 1) * wordLen);
            differ.put(word, differ.getOrDefault(word, 0) + 1);
        }
        for (String word : words) {
            differ.put(word, differ.getOrDefault(word, 0) - 1);
            if (differ.get(word) == 0) {
                differ.remove(word);
            }
        }
        for (int start = i; start <= ls - wordLen * wordsCount; start += wordLen) {
            if (start != i) {
                String word = s.substring(start + wordLen * (wordsCount - 1), start + wordLen * wordsCount);
                differ.put(word, differ.getOrDefault(word, 0) + 1);
                if (differ.get(word) == 0) {
                    differ.remove(word);
                }
                word = s.substring(start - wordLen, start);
                differ.put(word, differ.getOrDefault(word, 0) - 1);
                if (differ.get(word) == 0) {
                    differ.remove(word);
                }
            }
            if (differ.isEmpty()) {
                res.add(start);
            }
        }
    }
    return res;
}

時(shí)間復(fù)雜度：O(ls×n)，其中 ls 是輸入 s 的長度，n 是 words 中每個(gè)單詞的長度。需要做 n 次滑動(dòng)窗口，每次需要遍歷一次 s。
空間復(fù)雜度：O(m×n)，其中 m 是 words 的單詞數(shù)，n 是 words 中每個(gè)單詞的長度。每次滑動(dòng)窗口時(shí)，需要用一個(gè)哈希表保存單詞頻次。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

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