Minimum Window Substring 最小窗口子串

问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
[76] Minimum Window Substring  

https://leetcode.com/problems/minimum-window-substring/description/

* algorithms
* Hard (31.68%)
* Total Accepted:    267.2K
* Total Submissions: 841.8K
* Testcase Example:  '"ADOBECODEBANC"\n"ABC"'

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:


Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"


Note:


	If there is no such window in S that covers all characters in T, return the empty string "".
	If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

解析

据说窗口移动问题是疏通Array各种问题中的关键的关键。

这道Leetcode上难度为hard的题目显然就是传说中的不会做就是100年不会的题目。

看完别人的分析，我们来自己分析一下。

这个题目的核心就是，首先移动右边界，去寻找一个符合条件的字符串，记录下这个字符串的长度，然后移动左边界，直到去掉一个关键的字符，然后再试着移动右边界，去寻找一个比刚刚更短的符合条件的字符串。

详细来说，

首先，我们用一个hash来记录T中各个字符出现的次数。记做hash_t。

那么例子中，我们获得的hash_t就是{a=>1, b=>1, c=>1}。

接下来我们逐个遍历s中的每个字符,假设当前位置为i。每当我们遇到t中出现的字符，就将hash_t[s[i]]对应地减去1。

当hash_t[s[i]]为0的时候，我们知道我们已经找到了符合要求的一个字符，所以我们可以另外用一个cnt，初始值为0，每当hash_t[s[i]]为0，我们就将cnt加上1。
同时，我们将hash_t[s[i]]减去1。

想想一下我们可能遇到hash_t[s[i]] 为负数的情况，但是这个也不要紧，这说明当前字符串s中已经有了多个在t中出现的相同字符。

当cnt等于t的长度，说明我们已经找齐了所有的t中的字符，这个时候可以将当前从左边界到右边界的字符串和目前已经知道的最短符合条件的字符串进行比较。

接下来，移动左边界left。当左边界的字符不在我们hash_t中的时候，我们不断移动左边界。当左边字符在hash_t中，我们将hash_t[s[left]]加上1。并将cnt减去1.
当hash_t[s[left]]变为0以上，说明我们又缺乏了s[left],所以需要移动右边界去继续寻找。。。

Ruby 解法

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
def min_window(s, t)
  hash_t = {}
  t.split("").each do |c|
    hash_t[c] ||=0
    hash_t[c]+=1
  end
  cnt = 0
  left = 0
  min = 2**31 - 1
  result = ""
  for i in 0..s.length - 1
    right = s[i]
    if hash_t[right]
      hash_t[right] -=1
      cnt +=1 if hash_t[right] >= 0
    end
    while cnt == t.length
      if min > i - left + 1
        min = i - left + 1
        result = s[left...left+min]
      end
      if hash_t[s[left]]
        hash_t[s[left]] +=1
        cnt -=1 if hash_t[s[left]] > 0
      end
      left +=1
    end
  end
  return result
end

反思

刷题的话并不是要发明什么，所以百思不得其解的时候，去看一下答案还是有必要的。

leetcode

一筹莫展的LeetCode10 正则表达式匹配

基本上是一筹莫展的题目，果断时间再遇到估计也还是一筹莫展。

题目

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
67
68
69
70
71
72
73
[10] Regular Expression Matching  

https://leetcode.com/problems/regular-expression-matching/description/

* algorithms
* Hard (25.59%)
* Total Accepted:    333.7K
* Total Submissions: 1.3M
* Testcase Example:  '"aa"\n"a"'

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.


'.' Matches any single character.
'*' Matches zero or more of the preceding element.


The matching should cover the entire input string (not partial).

Note:


	s could be empty and contains only lowercase letters a-z.
	p could be empty and contains only lowercase letters a-z, and characters like . or *.


Example 1:


Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".


Example 2:


Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".


Example 3:


Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".


Example 4:


Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".


Example 5:


Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

解读

基本就是要考虑遇到.*以及*的时候。

举个例子来说，

1
2
s = "mississippi"
p = "mis*is*p*."

我们大可跳过前面不是特殊情况的完全匹配的部分，直到

1
2
s = "mi|ssissippi"
p = "mi|s*is*p*."

因为*可以匹配0到多个前面的字符s。所以，我们可以去试着递归匹配

1
2
3
4
5
6
7
8
9
s = "ssissippi"
p = "is*p*."


s = "sissippi"
p = "is*p*."

s = "issippi"
p = "is*p*."

所以基本流程是

  1. 当p长度为0，检查s是否长度为0，是的话返回true，否则返回false。
  2. 当p的长度为1， 检查s的长度是否为1，如果s长度为1，并且s和p相同亦或者p为”.”，则返回true，否则返回false。
  3. 当p[1]不为*的时候递归匹配s[1..-1] p[1..-1]。
  4. 当p[1]为*的时候，这个时候就麻烦了。因为*可以匹配0个到多个p[0]，所以我们得做一次循环，在循环中递归匹配。

Ruby 解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def is_match(s, p)
  return s.length == 0  if p.length == 0
  return s.length == 1 && (s[0] == p[0] || p[0] ==".") if p.length == 1
  if p[1] != "*"
    return false if s.length == 0
    return (s[0] == p[0] || p[0] ==".") && is_match(s[1..-1], p[1..-1])
  end
  temp = s
  while s.length != 0 && (s[0] == p[0] || p[0] == ".")
    result = is_match(s[1..-1], p[2..-1])
    return true if result == true
    s = s[1..-1]
  end
  return is_match(temp, p[2..-1])
end

后话

不看答案我是真的不会，看了答案我还是懵的。

算法 leetcode
e">
* algorithms
* Easy (34.02%)
* Total Accepted: 530.8K
* Total Submissions: 1.6M
* Testcase Example: '["flower","flow","flight"]'

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:


Input: ["flower","flow","flight"]
Output: "fl"


Example 2:


Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.


Note:

All given inputs are in lowercase letters a-z.

思路

首先对字符串数组进行排序，找到最短的字符串，那么我们知道最长前缀子字符串的长度是不可能超过这个最短字符串长度的。
然后我们就开始遍历，对于最短字符串中的每个元素，我们遍历整个字符串数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def longest_common_prefix(strs)
  return "" if strs.empty?
  sorted = strs.sort{|a| a.length}
  i = 0
  while i < sorted[0].length
    a  = sorted[0][i]
    j = 0
    while j < strs.length - 1
      j+=1
      return sorted[0][0...i] if sorted[j][i] != a
    end
    i += 1
  end
  return sorted[0]
end

后记

联想到生活中的一些目标，其实关键还是去分析自己缺乏什么解决问题的关键要素。
对症下药而不是盲目叠加自我满足感。

LeetCode