"Oneliners" in Python and C++


  • 4

    Well, one line in addition to copying&pasting my old solution for an old problem.

    class Solution(object):
        def checkInclusion(self, s1, s2):
            return len(self.minWindow(s2, s1)) == len(s1)
        
        # Copied&pasted old problem's solution
        def minWindow(self, s, t):
            need, missing = collections.Counter(t), len(t)
            i = I = J = 0
            for j, c in enumerate(s, 1):
                missing -= need[c] > 0
                need[c] -= 1
                if not missing:
                    while i < j and need[s[i]] < 0:
                        need[s[i]] += 1
                        i += 1
                    if not J or j - i <= J - I:
                        I, J = i, j
            return s[I:J]
    

    Edit: As pointed out by @FionaFang, another old problem is similar to this one (and its solution can be used here to create a "oneliner"):

    class Solution {
    public:
        bool checkInclusion(string s1, string s2) {
            return findAnagrams(s2, s1).size();
        }
        
        // Copied&pasted old problem's solution
        vector<int> findAnagrams(string s, string p) {
            int miss[256] = {}, missSum = p.size();
            for (char c : p)
                miss[c]++;
            vector<int> result;
            for (int i=0; i<s.size(); i++) {
                missSum -= miss[s[i]]-- > 0;
                int start = i+1 - p.size();
                if (!missSum)
                    result.push_back(start);
                missSum += start >= 0 && ++miss[s[start]] > 0;
            }
            return result;
        }
    };
    

  • 0

    Yes Stefan, it's much similar to find Anagrams problem.

    public boolean checkInclusion(String s1, String s2) {
        int [] map = new int [256];
        for (char ch : s1.toCharArray()) map [ch] ++;
        for (int idx = 0, start = 0; idx < s2.length(); idx ++) {
            char ch = s2.charAt (idx);
            if (-- map [ch] < 0) while (map [ch] != 0) map [s2.charAt (start ++)] ++;
             else if (idx - start + 1 == s1.length()) return true;
        }
        return false;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.