剑指offer

剑指offer017-含有所有字符的最短字符串

含有所有字符的最短字符串

Posted by 高明 on 2020-01-01

剑指offer017-含有所有字符的最短字符串

题目

给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 "" 。

如果 s 中存在多个符合条件的子字符串，返回任意一个。

 

注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。

 

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC" 
解释：最短子字符串 "BANC" 包含了字符串 t 的所有字符 'A'、'B'、'C'

示例 2：

输入：s = "a", t = "a"
输出："a"

示例 3：

输入：s = "a", t = "aa"
输出：""
解释：t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。

 

提示：

  • 1 <= s.length, t.length <= 105
  • s 和 t 由英文字母组成

 

进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？

 

注意：本题与主站 76 题相似（本题答案不唯一）：https://leetcode-cn.com/problems/minimum-window-substring/

Related Topics
  • 哈希表
  • 字符串
  • 滑动窗口

  • 👍 12
  • 👎 0

    • 思路

    错误想法1

    一开始想着记录所有的字符以及他们下标位置，这样就退化成了，字符串变位词问题

    比如 ADOBECODEBANC变成ABCBAC，然后找到ABC的变位词，这样的想法是错误的，因为变位词的要求是长度一致，但是这个长度是可以不一致的

    后面想到还是用滑动窗口，固定left从0开始，right从i到n

    一开始，先记录一下t字符串所需要的数据map

    1
    2
    3
    4
    5
    Map<Character, Integer> tMap = new HashMap<>();

    for (int i = 0; i < tLen; i++) {
        tMap.put(t.charAt(i), tMap.getOrDefault(t.charAt(i), 0) + 1);
    }

    比如：ABC

    1
    A:1 B:1 C:1

    新建一个窗口用于记录滑动窗口的数值内容

    1
    Map<Character, Integer> wins = new HashMap<>();

    左指针left从0开始

    1
    int left = 0;

    right从0-i

    1
    2
    3
    4
    5
    int left = 0;
    for (int i = 0; i < sLen; i++) {
        // 这样 left ~ i就是窗口
        // 窗口的每一个进来的值就是 i
    }

    主体逻辑，遍历到一个则放入窗口的map中

    1
    2
    3
    4
    5
    6
    for (int i = 0; i < sLen; i++) {
        // 放入窗口
        if (tMap.containsKey(s.charAt(i))) {
            wins.put(s.charAt(i), wins.getOrDefault(s.charAt(i), 0) + 1);
        }
    }

    当窗口map和符合条件时，并记录一下需要的信息，left要右移一位

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    while (tMap.size() == wins.size() && mapsContains(wins, tMap) && left <= i) {
        // 记录
        if (i - left + 1 < resSize) {
            resSize = i - left + 1;
            res = s.substring(left, i + 1);
        }
        
        char leftValue = s.charAt(left);
        if (wins.containsKey(leftValue)) {
            // 删除
            wins.put(leftValue, wins.get(leftValue) - 1);
        }
        left++;
    }

    这里为什么要用while，是因为left++之后，窗口可能也符合条件

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    import java.util.HashMap;
    import java.util.Map;

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String minWindow(String s, String t) {
            int sLen = s.length();
            int tLen = t.length();

            if (sLen < tLen) {
                return "";
            }

            Map<Character, Integer> tMap = new HashMap<>();

            for (int i = 0; i < tLen; i++) {
                tMap.put(t.charAt(i), tMap.getOrDefault(t.charAt(i), 0) + 1);
            }

            int left = 0;
            String res = "";
            int resSize = Integer.MAX_VALUE;

            Map<Character, Integer> wins = new HashMap<>();
            for (int i = 0; i < sLen; i++) {
                // 放入窗口
                if (tMap.containsKey(s.charAt(i))) {
                    wins.put(s.charAt(i), wins.getOrDefault(s.charAt(i), 0) + 1);
                }
                // 如果包含了 left+1 直到不包含
                while (tMap.size() == wins.size() && mapsContains(wins, tMap) && left <= i) {
                    // 记录
                    if (i - left + 1 < resSize) {
                        resSize = i - left + 1;
                        res = s.substring(left, i + 1);
                    }
                    char leftValue = s.charAt(left);
                    if (wins.containsKey(leftValue)) {
                        // 删除
                        wins.put(leftValue, wins.get(leftValue) - 1);
                    }
                    left++;
                }
            }
            return res;
        }

        public Boolean mapsContains(Map<Character, Integer> map1, Map<Character, Integer> map2) {
            if (map1.size() < map2.size()) {
                return false;
            }
            for (Character c :
                    map2.keySet()) {
                if (!map1.containsKey(c)) {
                    return false;
                }
                if (map1.get(c) < map2.get(c)) {
                    return false;
                }
            }

            return true;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    1
    2
    3
    解答成功:
    执行耗时:131 ms,击败了5.02% 的Java用户
    内存消耗:38.9 MB,击败了39.75% 的Java用户
    FEATURED TAGS
    剑指offer
    FRIENDS