Brooke

一、題目

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1's permutations is the substring of s2.

 

Example 1:

Input: s1 = "ab", s2 = "eidbaooo" Output: true Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input: s1 = "ab", s2 = "eidboaoo" Output: false

 

Constraints:

• 1 <= s1.length, s2.length <= 104
• s1 and s2 consist of lowercase English letters.

 

二、程式作法

/*寫法二*/
/*Sliding Window*/
public class Solution
{
    public bool CheckInclusion(String s1, String s2)
    {
        if (s1.Length > s2.Length)
            return false;

        int[] v1 = new int[26];
        int[] v2 = new int[26];

        for (int i = 0; i < s1.Length; i++)
            v1[s1[i] - 'a']++;

        for (int i = 0; i < s1.Length; i++)
            v2[s2[i] - 'a']++;

        if (Check(v1, v2))
            return true;

        if (s1.Length == s2.Length)
            return false;

        int ind = s1.Length;
        do
        {
            v2[s2[ind - s1.Length] - 'a']--;
            v2[s2[ind] - 'a']++;
            if (Check(v1, v2))
                return true;
            ind++;
        } while (ind < s2.Length);

        return false;
    }

    public bool Check(int[] v1, int[] v2)
    {
        for (int i = 0; i < 26; i++)
        {
            if (v1[i] != v2[i])
                return false;
        }
        return true;
    }
}

/*寫法一：Using sorting [Time Limit Exceeded]*/
/*
public class Solution
{
    public Boolean CheckInclusion(String s1, String s2)
    {
        s1 = sort(s1);
        for (int i = 0; i <= s2.Length - s1.Length; i++)
        {
            if (s1.Equals(sort(s2.Substring(i, s1.Length))))
                return true;
        }
        return false;
    }

    public String sort(String s)
    {
        char[] t = s.ToCharArray();
        Array.Sort(t);
        return new String(t);
    }
}
*/

 

三、思路筆記

目的為判斷字串 s1 是否為字串 s2 的排列組合之一。

• 思路一

我們可以根據 s1 的長度，一步一步地在 s2 裡比對，

先對 s1 做排序，然後每次在 s2 裡取跟 s1 一樣的長度排序後做比對，

如果一樣則代表 s1 是字串 s2 的排列組合之一。

但由於每次與 s2 子集比對時，都需先將 s2 子集作排序，

當 s2 長度越長時，這方法將會造成 TLE (Time Limit Exceeded)。

• 思路二

做法跟思路一一樣，只不過我們要想辦法解決排序所造成的問題，

由於 s1 與 s2 只會包含 26 個小寫英文字母，所以我們可以去個別紀綠 s1 與 s2 的所有字母的出現次數，

當兩者一樣時，則代表 s1 是字串 s2 的排列組合之一。