392. 判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
进阶：
如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
致谢：
特别感谢 @pbrother 添加此问题并且创建所有测试用例。

示例 1：
输入：s = “abc”, t = “ahbgdc”
输出：true

示例 2：
输入：s = “axc”, t = “ahbgdc”
输出：false


提示：

  • 0 <= s.length <= 100
  • 0 <= t.length <= 10^4
  • 两个字符串都只由小写字符组成。

思路：
双指针，利用贪心的思想，前面的字符能匹配就用前面的字符

  1. class Solution {
  2.     public boolean isSubsequence(String s, String t) {
  3.         int n = s.length(), m = t.length();
  4.         int j = 0;
  5.         for (int i = 0; i < m; i++) {
  6.             if (j < n && s.charAt(j) == t.charAt(i)) {
  7.                 j++;
  8.             }
  9.             if (j == n)
  10.                 break;
  11.         }
  12.         return j == n;
  13.     }
  14. }

792. 匹配子序列的单词数

给定字符串 S 和单词字典 words, 求 words[i] 中是 S 的子序列的单词个数。
示例:
输入:
S = “abcde”
words = [“a”, “bb”, “acd”, “ace”]
输出: 3
解释: 有三个是 S 的子序列的单词: “a”, “acd”, “ace”。

注意:

  • 所有在words和 S 里的单词都只由小写字母组成。
  • S 的长度在 [1, 50000]。
  • words 的长度在 [1, 5000]。
  • words[i]的长度在[1, 50]。

思路：
一个字符串匹配变成多个字符串匹配
解法一：类似于392的解法，每次处理一个字符变为每次处理一个字符的所有字符串。使用字符串仅由小写字母组成这一特性，将剩余子串放在其开头字符对应位置。
时间复杂度：O(N + M)
空间复杂度：O(M)

解法二：我自己想的方法

  1. 将S中不同字符出现的所有位置存下来，相同的字符出现的位置按从小到大的顺序存储
  2. 遍历words，依次处理每个字符串
  3. 使用二分，根据当前字符和前一字符的位置找到其在原串中能够最早出现的位置（也是贪心的思想）
  4. 如果能找到一个满足要求的子序列说明该字符是原串的某个子序列
  1. //方法一：
  2. class Solution {
  3.     public int numMatchingSubseq(String s, String[] words) {
  4.         List<List<Pair>> list = new ArrayList<>();
  5.         for (int i = 0; i < 26; i++)
  6.             list.add(new ArrayList<>());
  8.         for (int i = 0; i < words.length; i++) {
  9.             int idx = words[i].charAt(0) - 'a';
  10.             list.get(idx).add(new Pair(i, 0));
  11.         }
  13.         int res = 0;
  14.         for (int i = 0; i < s.length(); i++) {
  15.             int idx = s.charAt(i) - 'a';
  16.             List<Pair> buf = new ArrayList<>();
  18.             for (Pair pp : list.get(idx)) {
  19.                 if (pp.y + 1 == words[pp.x].length())
  20.                     res++;
  21.                 else
  22.                     buf.add(new Pair(pp.x, pp.y + 1));
  23.             }
  24.             list.get(idx).clear();
  25.             for (Pair pp : buf) {
  26.                 int idx2 = words[pp.x].charAt(pp.y) - 'a';
  27.                 list.get(idx2).add(pp);
  28.             }
  29.         }
  30.         return res;
  32.     }
  33. }
  34. class Pair {
  35.     int x, y;
  36.     Pair(int x, int y) {
  37.         this.x = x;
  38.         this.y = y;
  39.     }
  40. }
  1. //方法二：
  2. class Solution {
  3.     public int numMatchingSubseq(String s, String[] words) {
  4.         List<List<Integer>> map = new ArrayList<>();
  5.         for (int i = 0; i < 26; i++)
  6.             map.add(new ArrayList<>());
  8.         for (int i = 0; i < s.length(); i++) {
  9.             int idx = s.charAt(i) - 'a';
  10.             map.get(idx).add(i);
  11.         }
  13.         // int pp = 0;
  14.         // for (List<Integer> list : map)
  15.         //     System.out.println((char)(pp++ + 'a') + " " + list.toString());
  17.         int res = 0;
  18.         for (String word : words) {
  19.             int pre = -1;
  20.             boolean flag = true;
  21.             for (int i = 0; i < word.length(); i++) {
  22.                 int j = word.charAt(i) - 'a';
  23.                 if (map.get(j).size() == 0) {
  24.                     flag = false;
  25.                     break;
  26.                 }
  27.                 int l = 0, r = map.get(j).size() - 1;
  28.                 while (l < r) {
  29.                     int mid = l + r >> 1;
  30.                     if (map.get(j).get(mid) <= pre)
  31.                         l = mid + 1;
  32.                     else 
  33.                         r = mid;
  34.                 }
  35.                 int x = map.get(j).get(l);
  36.                 // System.out.println(x);
  37.                 if (x > pre) {
  38.                     pre = x; 
  39.                 } else {
  40.                     flag = false;
  41.                     break;
  42.                 }
  43.             }
  44.             if (flag)
  45.                 res++;
  46.         }
  47.         return res;
  48.     }
  49. }

方法3：
有限状态机，类似于727(从残酷群主那学来的)
预处理S，存储每个字符的下一字符(26个)的位置，这样判断字典中的每个字符串时只需要O(N)的时间复杂度。其中O(N)指字典中该字符串的长度。
当然这样做的时间复杂度肯定会大于方法2的。

  1. class Solution {
  2.     public int numMatchingSubseq(String s, String[] words) {
  3.         int n = s.length();
  4.         s = " " + s;
  5.         int[][] ne = new int[n + 1][26];
  7.         //最后一个元素右边啥都没了，指向-1
  8.         for (int i = 0; i < 26; i++)
  9.             ne[n][i] = -1;
  11.         for (int i = n - 1; i >= 0; i--) {
  12.             for (int j = 0; j < 26; j++) {
  13.                 ne[i][j] = ne[i + 1][j];
  14.                 if (s.charAt(i + 1) - 'a' == j)
  15.                     ne[i][j] = i + 1;
  16.             }
  17.         }
  19.         int cnt = 0;
  20.         for (String w: words) {
  21.             int idx = 0;
  22.             boolean flag = true;
  23.             for (int i = 0; i < w.length(); i++) {
  24.                 idx = ne[idx][w.charAt(i) - 'a'];
  25.                 if (idx == -1) {
  26.                     flag = false;
  27.                     break;
  28.                 }
  29.             }
  31.             if (flag)
  32.                 cnt++;
  33.         }
  35.         return cnt;
  36.     }
  37. }

76. 最小覆盖子串

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

注意：

  • 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串，我们保证它是唯一的答案。

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

示例 1：
输入：s = “ADOBECODEBANC”, t = “ABC” 输出：“BANC”
示例 2：
输入：s = “a”, t = “a” 输出：“a”
示例 3:
输入: s = “a”, t = “aa” 输出: “” 解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中， 因此没有符合条件的子字符串，返回空字符串。

提示：

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

思路：
方法1：
哈希表 + 滑动窗口 + 个数判断

  1. // 方法1
  2. class Solution {
  3.     public String minWindow(String s, String t) {
  4.         int n = s.length(), m = t.length();
  5.         if (m > n) return "";
  6.         int[] map = new int[128];
  7.         int diff = 0;
  9.         for (int i = 0; i < m; i++)
  10.             map[t.charAt(i)]--;
  11.         for (int x : map)
  12.             if (x != 0)
  13.                 diff++;
  15.         int len = n, l = -1, r = -1;
  16.         for (int i = 0, j = 0, cnt = 0; i < n; i++) {
  17.             char cur = s.charAt(i);
  18.             map[cur]++;
  19.             if (map[cur] == 0) cnt++;
  20.             while (cnt == diff && map[s.charAt(j)] > 0) {
  21.                 map[s.charAt(j)]--;
  22.                 j++;
  23.             }
  24.             if (cnt == diff && i - j + 1 <= len) {
  25.                 len = i - j + 1;
  26.                 l = j;
  27.                 r = i;
  28.             }
  29.         }
  30.         return l == -1 ? "" : s.substring(l, r + 1);
  31.     }
  32. }

139. 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典，判定 s 是否可以由空格拆分为一个或多个在字典中出现的单词。
说明：拆分时可以重复使用字典中的单词。

示例 1：
输入: s = “leetcode”, wordDict = [“leet”, “code”] 输出: true 解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。
示例 2：
输入: s = “applepenapple”, wordDict = [“apple”, “pen”] 输出: true 解释: 返回 true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。 注意你可以重复使用字典中的单词。
示例 3：
输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”] 输出: false

提示：

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s 和 wordDict[i] 仅有小写英文字母组成
  • wordDict 中的所有字符串 互不相同

思路：
DP
判断一个给定字符串**s**是否属于给定列表中的字符串的判断方式

  • 哈希表：每次都得对s求哈希(O(s.length())，复杂度较高
  • 字典树：常数能比哈希表小点O(s.length())，线性扫描s就能得出在或不在
  • 字符串哈希：可以直接计算出哈希值O(1)，较哈希表来说快了不少，但不能保证一定对！
  1. //DP + 字符串哈希
  2. class Solution {
  3.     public boolean wordBreak(String s, List<String> wordDict) {
  4.         Set<Long> set = new HashSet<>();
  5.         int n = s.length();
  6.         final int P = 131;
  7.         for (String ss : wordDict) {
  8.             long h = 0;
  9.             for (int i = 0; i < ss.length(); i++) {
  10.                 h = h * P + ss.charAt(i); 
  11.             }
  12.             set.add(h);
  13.         }
  15.         s = " " + s;
  16.         long[] h = new long[n + 1];
  17.         long[] pow = new long[n + 1];
  18.         pow[0] = 1;
  19.         for (int i = 1; i <= n; i++) {
  20.             h[i] = h[i - 1] * P + s.charAt(i);
  21.             pow[i] = pow[i - 1] * P;
  22.         }
  24.         boolean[] f = new boolean[n + 1];
  25.         f[0] = true;
  27.         for (int i = 1; i <= n; i++) {
  28.             for (int j = 1; j <= i; j++) {
  29.                 if (!f[j - 1]) continue;
  30.                 long hash = h[i] - h[j - 1] * pow[i - j + 1];
  31.                 if (set.contains(hash)) {
  32.                     f[i] = true;
  33.                     break;
  34.                 }
  35.             }
  36.         }
  37.         return f[n];
  38.     }
  39. }

727. Minimum Window Subsequence 最小窗口序列

会员题

突然发现这道题和76几乎一模一样，76是包含大小写字母，这道题是仅包含小写字母！ 但是不同点在于这道题要求顺序也一致，而76没有该限制

Given strings S and T, find the minimum (contiguous) substring W of S, so that T is a subsequence of W.
If there is no such window in S that covers all characters in T, return the empty string “”. If there are multiple such minimum-length windows, return the one with the left-most starting index.
Example 1:
Input: S = “abcdebdde”, T = “bde” Output: “bcde” Explanation: “bcde” is the answer because it occurs before “bdde” which has the same length. “deb” is not a smaller window because the elements of T in the window must occur in order.

Note:

  • All the strings in the input will only contain lowercase letters.
  • The length of S will be in the range [1, 20000].
  • The length of T will be in the range [1, 100].

问题描述：
从字符串S中找最短子串，其子序列包含字符串T。

思路：
暴力方法：一次从每个S的字符开始与T进行双指针匹配，时间复杂度O(N2)
方法一：双序列DP
状态表示：f[i][j]表示S中以i结尾的包含T的子串[1, j]的子串的长度。
状态转移：

  1. S: x x x x {x x x x x i}
  2. T: [y y y y y y j]
  3. 很明显看出
  4. 若S[i] == T[j]   f[i][j] = f[i - 1][j - 1] + 1
  5. 若S[i] != T[j]   f[i][j] = f[i - 1][j] + 1

初始化f[i][0] = 0, f[0][j] = INF, f[0][0] = 0
最终取min(f[i][M])即可
时间复杂度：O(N*M)
方法二：有限状态机。预处理每一个位置的字符其后26个字母第一次出现的位置。
这样就能快速找到T中下一个字符在S中的位置。时间复杂度为O(KN)，len是T的第一个字母在S中出现的次数
解释：遍历S中每个T的首字符然后利用有限自动机向后匹配共len次，每次最长匹配len(T)个字符，而预处理的时间复杂度为O(26N)，所以总时间复杂度差不多为O(KN)，K不定，总之是O(n)级别的。

  1. // 方法1
  2. class Solution {
  3.     public String minWindow(String s, String t) {
  4.         int n = s.length(), m = t.length();
  5.         s = " " + s;
  6.         t = " " + t;
  7.         int[][] f = new int[n + 1][m + 1];
  8.         int INF = 0x3f3f3f3f;
  9.         for (int j = 1; j <= m; j++)
  10.             f[0][j] = INF;
  11.         for (int i = 0; i <= n; i++)
  12.             f[i][0] = 0;
  14.         int res = INF, l = -1, r = -1;
  15.         for (int i = 1; i <= n; i++) {
  16.             for (int j = 1; j <= m; j++) {
  17.                 f[i][j] = INF;
  18.                 if (s.charAt(i) == t.charAt(j))
  19.                     f[i][j] = f[i - 1][j - 1] + 1;
  20.                 else
  21.                     f[i][j] = f[i - 1][j] + 1;
  22.             }
  23.             if (f[i][m] < res) {
  24.                 res = f[i][m];
  25.                 l = i - f[i][m] + 1;
  26.                 r = i;
  27.             }
  28.         }
  29.         return l == -1 ? "" : s.substring(l, r + 1); 
  30.     }
  31. }
  1. //方法2
  2. class Solution {
  3.     public String minWindow(String s, String t) {
  4.         int n = s.length();
  5.         s = " " + s;
  6.         int[][] ne = new int[n + 1][26];
  7.         for (int i = 0; i < 26; i++)
  8.             ne[n][i] = -1;
  9.         for (int i = n - 1; i >= 0; i--) {
  10.             for (int j = 0; j < 26; j++) {
  11.                 ne[i][j] = ne[i + 1][j];
  12.                 if (s.charAt(i + 1) - 'a' == j)
  13.                     ne[i][j] = i + 1;
  14.             }
  15.         }
  17.         List<Integer> list = new ArrayList<>();
  18.         for (int i = 0; i < s.length(); i++)
  19.             if (s.charAt(i) == t.charAt(0))
  20.                 list.add(i);
  22.         int res = 0x3f3f3f3f, l = -1, r = -1;
  23.         for (int x : list) {
  24.             int idx = x - 1;
  25.             for (int i = 0; i < t.length(); i++) {
  26.                 idx = ne[idx][t.charAt(i) - 'a'];
  27.                 if (idx == -1)
  28.                     break;
  29.             }
  30.             if (idx != -1) {
  31.                 int len = idx - x + 1;
  32.                 if (len < res) {
  33.                     l = x;
  34.                     r = idx;
  35.                     res = len;
  36.                 }
  37.             }
  38.         }
  39.         if (l != -1)
  40.             return s.substring(l, r + 1);
  41.         return "";
  42.     }
  43. }

524. 通过删除字母匹配到字典里最长单词

给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。

示例 1：
输入：s = “abpcplea”, dictionary = [“ale”,”apple”,”monkey”,”plea”] 输出：“apple”
示例 2：
输入：s = “abpcplea”, dictionary = [“a”,”b”,”c”] 输出：“a”

提示：

  • 1 <= s.length <= 1000
  • 1 <= dictionary.length <= 1000
  • 1 <= dictionary[i].length <= 1000
  • s 和 dictionary[i] 仅由小写英文字母组成

思路：
与792基本一致！
方法一：贪心 + 双指针
题目要求输出最长的且字典序最小的符合要求的字符串，故可对字符串数组中的字符串按要求排好序，从前往后处理每一个字符串，一旦碰到符合要求的返回即可。
每个字符串的处理与392题方法一致。
时间复杂度最差为O(n2logn)
方法二：贪心 + 有限自动机
类似于727的处理。
时间复杂度最差为O(n2logn)

  1. // 方法1
  2. class Solution {
  3.     public String findLongestWord(String s, List<String> dictionary) {
  4.         int n = s.length();
  5.         Collections.sort(dictionary, (o1, o2) -> (o2.length() == o1.length() ? o1.compareTo(o2) : o2.length() - o1.length()));
  7.         for (String ss : dictionary) {
  8.             int j = 0;
  9.             boolean flag = true;
  10.             for (int i = 0; i < ss.length(); i++) {
  11.                 char ch = ss.charAt(i);
  12.                 while (j < n && s.charAt(j) != ch)
  13.                     j++;
  14.                 if (j == n) {
  15.                     flag = false;
  16.                     break;
  17.                 }
  18.                 j++;
  19.             }
  20.             if (flag) return ss;
  21.         }
  22.         return "";
  23.     }
  24. }
  1. // 方法2
  2. class Solution {
  3.     public String findLongestWord(String s, List<String> dictionary) {
  4.         int n = s.length();
  6.         s = " " + s;
  7.         int[][] ne = new int[n + 1][26];
  8.         for (int i = 0; i < 26; i++)
  9.             ne[n][i] = -1;
  10.         for (int i = n - 1; i >= 0; i--) {
  11.             for (int j = 0; j < 26; j++) {
  12.                 ne[i][j] = ne[i + 1][j];
  13.                 if (s.charAt(i + 1) - 'a' == j)
  14.                     ne[i][j] = i + 1;
  15.             }
  16.         }
  18.         Collections.sort(dictionary, (o1, o2) -> (o1.length() == o2.length() ? o1.compareTo(o2) : o2.length() - o1.length()));
  20.         for (String ss : dictionary) {
  21.             boolean flag = true;
  22.             int idx = 0;
  23.             for (int i = 0; i < ss.length(); i++) {
  24.                 idx = ne[idx][ss.charAt(i) - 'a'];
  25.                 if (idx == -1) {
  26.                     flag = false;
  27.                     break;
  28.                 }
  29.             }
  30.             if (flag)
  31.                 return ss;
  32.         }
  33.         return "";
  34.     }
  35. }

466. 统计重复个数

定义 str = [s, n] 表示 str 由 n 个字符串 s 连接构成。

  • 例如，str == [“abc”, 3] ==”abcabcabc” 。

如果可以从 s2 中删除某些字符使其变为 s1，则称字符串 s1 可以从字符串 s2 获得。

  • 例如，根据定义，s1 = “abc” 可以从 s2 = “ab_dbe_c” 获得，仅需要删除加粗且用斜体标识的字符。

现在给你两个字符串 s1 和 s2 和两个整数 n1 和 n2 。由此构造得到两个字符串，其中 str1 = [s1, n1]、str2 = [s2, n2] 。
请你找出一个最大整数 m ，以满足 str = [str2, m] 可以从 str1 获得。

示例 1：
输入：s1 = “acb”, n1 = 4, s2 = “ab”, n2 = 2 输出：2
示例 2：
输入：s1 = “acb”, n1 = 1, s2 = “acb”, n2 = 1 输出：1

提示：

  • 1 <= s1.length, s2.length <= 100
  • s1 和 s2 由小写英文字母组成
  • 1 <= n1, n2 <= 106

思路：
找循环节
即找到s1使用多少次能满足下一次从s1开头匹配s2的某个位置正好在之前出现过，说明此时找到了循环节
最坏情况下需要找多少次呢？
s1的长度为n1， s2的长度为n2，根据抽屉原理，最多需要O(n1 * n2)次即可
找到循环节后，计算该循环节是由多少个s1组成的，每个循环节能匹配多长的s2中的字符
剩余s1中的字符可以暴力继续处理

  1. class Solution {
  2.     public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
  3.         int[] cnt = new int[n1];
  4.         Map<Integer, Integer> map = new HashMap<>();
  5.         int len1 = s1.length(), len2 = s2.length();
  6.         for (int i = 0, k = 0; i < n1; i++) {
  7.             for (int j = 0; j < len1; j++) {
  8.                 if (s1.charAt(j) == s2.charAt(k % len2))
  9.                     k++;
  10.             }
  11.             cnt[i] = k;
  12.             if (map.containsKey(k % len2)) {
  13.                 int l = map.get(k % len2);
  14.                 int size = i - l;
  15.                 int c = k - cnt[l];
  16.                 int sum = (n1 - i - 1) / size * c;
  17.                 for (int u = 0; u < (n1 - i - 1) % size; u++) {
  18.                     for (int j = 0; j < len1; j++) {
  19.                         if (s1.charAt(j) == s2.charAt(k % len2)) {
  20.                             k++;
  21.                         }
  22.                     }
  23.                 }
  24.                 return (sum + k) / len2 / n2;
  25.             }
  26.             map.put(k % len2, i);
  27.         }
  28.         return cnt[n1 - 1] / len2 / n2;
  29.     }
  30. }