字母异位词&赎金信&最小覆盖子串&字符串的排列&串连所有单词的子串

字母异位词分组

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

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

说明：

  • 所有输入均为小写字母。
  • 不考虑答案输出的顺序。

方法一：排序数组分类
维护一个映射，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());
}

时间复杂度：O(NKlogK)，其中 N 是 strs 的长度，而 K 是 strs 中字符串的最大长度

方法二：按计数分类
根据每个字符串中字母出现的次数构造字符串，作为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());
}

时间复杂度O(NK)

找到字符串中所有字母异位词

给定一个字符串 s和一个非空字符串 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" 的字母异位词

方法一：暴力（超时）
依次判断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;
}

用计数法可以通过

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

方法二：滑动窗口
先用一个map存在p中字母存在的次数，再用一个map存滑动窗口中字母存在的次数
滑动窗口指针i,j，每次j向右移动，更新j对应字母出现的次数，如果比p中map的大，i指针向右移动，直到不比map大，i在移动过程中也要更新次数，如果窗口大小和p的长度相等，说明找到了一个满足条件的值

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

有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t中每个字符出现的次数都相同，则称 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;
}

只统计一个字符串：

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

赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

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

magazine 中的每个字符只能在 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;
}

最小覆盖子串

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

示例：

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

说明：

  • 如果 S 中不存这样的子串，则返回空字符串 ""。
  • 如果 S 中存在这样的子串，我们保证它是唯一的答案。

方法一：暴力（超时）
枚举s所有的子串，统计字符的频数看是否符合条件

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) {//优化，区间比找到的长度更长就不用考虑了
                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;//小优化，不用往右边找了
            }
        }
    }
    return ans;
}

时间复杂度O(s3+t)

小优化：直接在循环中统计频数

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) {//优化，区间比找到的长度更长就不用考虑了
                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;//小优化，不用往右边找了
            }
        }
    }
    return ans;
}

方法二：滑动窗口
滑动窗口中的都是满足条件的，移动左边界找到最小的子串

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;//滑动窗口中包含t中字符的个数，不重复计算
    while (right < s.length()) {
        char rightChar = s.charAt(right);
        if (tMap[rightChar] == 0) {//这个判断其实可以删掉
            right++;
            continue;
        }
        if (sMap[rightChar] < tMap[rightChar]) {
            distance++;
        }
        sMap[rightChar]++;
        right++;
        while (distance == t.length()) {//滑动窗口包含了t中所有字符，移动左边界
            if (right - left <= minLen) {
                minLen = right - left;
                ans = s.substring(left, right);
            }
            char leftChar = s.charAt(left);
            if (tMap[leftChar] == 0) {//这个判断其实可以删掉
                left++;
                continue;
            }
            if (sMap[leftChar] == tMap[leftChar]) {
                distance--;
            }
            sMap[leftChar]--;
            left++;
        }
    }
    return ans;
}

时间复杂度O(s+t)：右边界s，最坏情况下左边界s-t

不用存s的频数

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();//滑动窗口中包含还差t中字符的个数
    while (right < s.length()) {
        char rightChar = s.charAt(right);
        if (tMap[rightChar] > 0) {
            distance--;
        }
        tMap[rightChar]--;
        right++;
        while (distance == 0) {//滑动窗口包含了t中所有字符，移动左边界
            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;
}

字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

示例 1：

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

示例 2：

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

相当给你一个 S 和一个 T，请问你 S 中是否存在一个子串，包含 T 中所有字符且不包含其他字符？

滑动窗口

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

串联所有单词的子串

给定一个字符串 s和一个字符串数组 words。 words 中所有字符串 长度相同。
s中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

  • 例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s中的开始索引。你可以以 任意顺序 返回答案。

示例 1：

输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2：

输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
解释：因为words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

用哈希表统计

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

滑动窗口
此题是438. 找到字符串中所有字母异位词的进阶版。不同的是第 438 题的元素是字母，而此题的元素是单词，可以用类似的方法二的滑动窗口来解这题。

记 words 的长度为 m，words 中每个单词的长度为 n，s 的长度为 ls。首先需要将 s 划分为单词组，每个单词的大小均为 n （首尾除外）。这样的划分方法有 n 种，即先删去前 i （i=0∼n−1）个字母后，将剩下的字母进行划分，如果末尾有不到 n 个字母也删去。对这 n 种划分得到的单词数组分别使用滑动窗口对 words 进行类似于「字母异位词」的搜寻。

划分成单词组后，一个窗口包含 s 中前 m 个单词，用一个哈希表 differ 表示窗口中单词频次和 words 中单词频次之差。初始化 differ 时，出现在窗口中的单词，每出现一次，相应的值增加 1，出现在 words 中的单词，每出现一次，相应的值减少 1。然后将窗口右移，右侧会加入一个单词，左侧会移出一个单词，并对 differ 做相应的更新。窗口移动时，若出现 differ 中值不为 0 的键的数量为 0，则表示这个窗口中的单词频次和 words 中单词频次相同，窗口的左端点是一个待求的起始位置。划分的方法有 n 种，做 n 次滑动窗口后，即可找到所有的起始位置。

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

时间复杂度：O(ls×n)，其中 ls 是输入 s 的长度，n 是 words 中每个单词的长度。需要做 n 次滑动窗口，每次需要遍历一次 s。
空间复杂度：O(m×n)，其中 m 是 words 的单词数，n 是 words 中每个单词的长度。每次滑动窗口时，需要用一个哈希表保存单词频次。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 219,869评论 6赞 508
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 93,716评论 3赞 396
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 166,223评论 0赞 357
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 59,047评论 1赞 295
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 68,089评论 6赞 395
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,839评论 1赞 308
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,516评论 3赞 420
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 39,410评论 0赞 276
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,920评论 1赞 319
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 38,052评论 3赞 340
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 40,179评论 1赞 352
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,868评论 5赞 346
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,522评论 3赞 331
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 32,070评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,186评论 1赞 272
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 48,487评论 3赞 375
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 45,162评论 2赞 356