string - 查找包含另一个字符串作为子序列的最小子字符串的长度

Question

假设我有一个 strings1 = "eabegcghdefgh"和另一个 string s2 = "egh"。

代码应该返回答案4"efgh"，因为它的子字符串s1（因为它是作为子序列包含的最小子字符串s2）。

注意：可能有几个子字符串，但这"efgh"是最小的子字符串。

换句话说，找到s1包含另一个字符串的所有字符的最小子字符串的长度s2，但要按顺序。

请注意：我想问如何在 O(n) 时间复杂度中做到这一点。

标签： stringalgorithmdata-structurestime-complexity

Answer 1

public static String smallestWindow(String S, String T) {
    if (S.equals(T))  //If S and T are equal, then simply return S.
        return S;
    /**
     * Use sliding window. 

如果存在 S 的子串 W 使得 T 是 W 的子序列，则 S 的比 W 长或具有相同长度的子串也必须存在。因此，从 S 中的索引 0 和 T 中的索引 0 开始找到 S 的这样一个子串。如果到达 T 的最后一个字符，则 S 中的当前索引是子串的结束索引，并找到最大可能的开始索引S 中的子串。找到起始索引和结束索引后，可以更新最小窗口大小，同时存储起始索引和结束索引。

然后将 T 中的索引设置为 0，并尝试在 S 中找到另一个子字符串。重复该过程，直到到达 S 的末尾。访问完 S 中的所有字符后，可以得到最小的子串长度，并返回最短的子串。

     */
    int sLength = S.length(), tLength = T.length();
    int start = 0, end = sLength - 1;
    int sIndex = 0, tIndex = 0;
    while (sIndex < sLength) {
        if (S.charAt(sIndex) == T.charAt(tIndex))
            tIndex++;
        if (tIndex == tLength) {
            int rightIndex = sIndex;
            tIndex--;
            while (tIndex >= 0) {
                if (S.charAt(sIndex) == T.charAt(tIndex))
                    tIndex--;
                sIndex--;
            }
            sIndex++;
            if (rightIndex - sIndex < end - start) {
                start = sIndex;
                end = rightIndex;
            }
            tIndex = 0;
        }
        sIndex++;
    }
    int windowSize = end - start + 1;
        return S.substring(start, start + windowSize);
}