leetcode/PermutationInString

Permutation in String

是否存在等价子串

my solution

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        if (s2.size() < s1.size()) return false;

        map<char, int> mp;
        for (auto &v : s1) ++mp[v];

        for (int i = 0, b = 0; i < s2.size(); ++i) {
            if (!mp.count(s2[i])) {
                while (b < i && mp.count(s2[b]) != 0)
                    ++mp[s2[b++]];
                b = i + 1;
            } else if (--mp[s2[i]] < 0) {
                while (mp[s2[i]] < 0)
                    ++mp[s2[b++]];
            }

            if (i - b == s1.size() - 1) return true;
            if (s2.size() - b < s1.size()) return false;
        }

        return false;
    }
};

用的是滑动窗口来做. 其中 map 存放元素. 不过可以不用高级数据结构. 因为小写英文字母总共也就 26 个, 其下标做索引. 还可以省去一个 int. 有一些优化的点, 可以通过最优算法来借鉴.

the best solution

class Solution {
public:

    bool match(int map1[], int map2[])
    {
        for (int i = 0; i < 26; i++)
        {
            if (map1[i] != map2[i])
                return false;
        }
        return true;
    }

    bool checkInclusion(string str, string text)
    {
        if(str.length() > text.length())
            return false;
        int *textMap = (int*)calloc(26, sizeof(int));
        int *strMap = (int *)calloc(26, sizeof(int));
        // creating the maps with the relevant chars
        for (int i = 0; i < str.length(); i++)
        {
            textMap[text[i] - 'a']++;
            strMap[str[i] - 'a']++;
        }
        // sliding window
        for (int i = 0; i < text.length() - str.length(); i++)
        {
            if(match(strMap, textMap))
                return true;
            textMap[text[i + str.length()] - 'a']++;
            textMap[text[i] - 'a']--;
        }
        return match(strMap, textMap);
    }
};

一个关键的点是我不必一开始就将所有的 s2 获取. 这是我没想到的. (其实这也不难想到, 为什么呢 = =)

他也是滑动窗口. 这没有什么特别好说的. 这里顺便说一下 calloc. 这是一个附带初始化的 malloc.