76. 最小覆盖子串

深藏阁楼爱情的钟 2023-10-04 10:26 6阅读 0赞

给你一个字符串 `s` 、一个字符串 `t` 。返回 `s` 中涵盖 `t` 所有字符的最小子串。如果 `s` 中不存在涵盖 `t` 所有字符的子串，则返回空字符串 `""` 。

**注意：**如果 `s` 中存在这样的子串，我们保证它是唯一的答案。

**示例 1：**

输入：s = "ADOBECODEBANC", t = "ABC"
    输出："BANC"

**示例 2：**

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

**提示：**

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

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

package Solution76;
    
    class Solutiontimeout {
    
    	public String minWindow(String s, String t) {
    		int tlen=t.length();
    
    		int start = 0;
    		int end = 0;
    		int min = Integer.MAX_VALUE;
    		for (int i = 0; i < s.length(); i++) {
    			for (int j = i + tlen; j <= s.length(); j++) {
    				// System.out.println(s.substring(i, j));
    				if (contain(s.substring(i, j), t)) {
    					if ((j - i) < min) {
    						min = j - i;
    						start = i;
    						end = j;
    					}
    
    				}
    			}
    		}
    		return s.substring(start, end);
    	}
    
    	public boolean contain(String s, String t) {
    		for (int i = 0; i < t.length(); i++) {
    			String temp = s.replaceFirst(t.substring(i, i + 1), "");
    			if (temp.length() != s.length() - 1) {
    				return false;
    			}
    			s = temp;
    		}
    		return true;
    	}
    
    	public static void main(String[] args) {
    
    		Solutiontimeout sol = new Solutiontimeout();
    		String s = "ADOBECODEBANC", t = "ABC";
    
    		System.out.println(sol.minWindow(s, t));
    
    	}
    
    }

超时

发表评论取消回复

表情：

评论列表（有 0 条评论，6人围观）

还没有评论，来说两句吧...

相关阅读

相关 76. 最小覆盖子串

给你一个字符串 `s` 、一个字符串 `t` 。返回 `s` 中涵盖 `t` 所有字符的最小子串。如果 `s` 中不存在涵盖 `t` 所有字符的子串，则返回空字符串 `""`

深藏阁楼爱情的钟/ 2023年10月04日 10:26/ 0 赞/ 7 阅读

相关 LeetCode - 76 最小覆盖子串

目录题目来源题目描述示例提示题目解析算法源码 -------------------- 题目来源 [76. 最小覆盖子串 - 力扣（LeetC

水深无声/ 2023年09月23日 16:57/ 0 赞/ 103 阅读

相关 leetcode 76 最小覆盖子串

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。示例：输入: S = "ADOBECODEBANC", T = "ABC"

不念不忘少年蓝@/ 2023年06月26日 03:18/ 0 赞/ 2 阅读

相关 LeetCode76--最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。注意：如果 s 中存

谁践踏了优雅/ 2023年01月13日 05:48/ 0 赞/ 115 阅读

相关【LeetCode 76】最小覆盖子串

题目描述给你一个字符串 S、一个字符串 T 。请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。示例：

妖狐艹你老母/ 2022年11月25日 11:43/ 0 赞/ 162 阅读

相关 LeetCode 76. 最小覆盖子串

76. 最小覆盖子串给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “”

系统管理员/ 2022年11月07日 05:55/ 0 赞/ 208 阅读

相关 LeetCode 76. 最小覆盖子串

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

淡淡的烟草味﹌/ 2022年10月27日 06:16/ 0 赞/ 168 阅读

相关 76. 最小覆盖子串

链接：[https://leetcode-cn.com/problems/minimum-window-substring/][https_leetcode-cn.com_pr

电玩女神/ 2022年10月13日 01:55/ 0 赞/ 186 阅读

相关 76. 最小覆盖子串

先上滑动窗口模板 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubm

﹏ヽ暗。殇╰゛Y/ 2022年10月09日 12:10/ 0 赞/ 192 阅读

相关 [leetcode] 76. 最小覆盖子串

[76. 最小覆盖子串][76.] 脑子不清醒的时候，不要刷题，不要刷题，不要刷题。。。。我这么困，为什么要刷题！在串S上维护i，j两个指针，i表示当前包含T所

痛定思痛。/ 2021年09月29日 12:58/ 0 赞/ 271 阅读