567. Permutation in String

LeetCode medium original: C# #array #csharp #leetcode #medium #sliding-window #string

Le texte du problème est traduit du russe pour la langue sélectionnée. Le code reste inchangé.

LeetCode Static

given две строки s1 и s2. return true, если s2 содержит перестановку s1, или false в противном случае.

Другими словами, return true, если одна из перестановок s1 является подстрокой s2.

Exemple:

Input: s1 = "ab", s2 = "eidbaooo"

Output: true

Explanation: s2 contains one permutation of s1 ("ba").

C# solution

correspondant/original

public class Solution {
    public bool CheckInclusion(string s1, string s2) {
        int s1Len = s1.Length, s2Len = s2.Length;
        if (s1Len > s2Len) return false;
        
        int[] s1Count = new int[26];
        int[] s2Count = new int[26];
        
        for (int i = 0; i < s1Len; i++) {
            s1Count[s1[i] - 'a']++;
            s2Count[s2[i] - 'a']++;
        }
        
        for (int i = 0; i < s2Len - s1Len; i++) {
            if (s1Count.SequenceEqual(s2Count)) return true;
            s2Count[s2[i] - 'a']--;
            s2Count[s2[i + s1Len] - 'a']++;
        }
        
        return s1Count.SequenceEqual(s2Count);
    }
}

C++ solution

brouillon automatique, à relire avant soumission

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool CheckInclusion(string s1, string s2) {
        int s1Len = s1.size(), s2Len = s2.size();
        if (s1Len > s2Len) return false;
        
        vector<int>& s1Count = new int[26];
        vector<int>& s2Count = new int[26];
        
        for (int i = 0; i < s1Len; i++) {
            s1Count[s1[i] - 'a']++;
            s2Count[s2[i] - 'a']++;
        }
        
        for (int i = 0; i < s2Len - s1Len; i++) {
            if (s1Count.SequenceEqual(s2Count)) return true;
            s2Count[s2[i] - 'a']--;
            s2Count[s2[i + s1Len] - 'a']++;
        }
        
        return s1Count.SequenceEqual(s2Count);
    }
}

Java solution

correspondant/original

public class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int s1Len = s1.length(), s2Len = s2.length();
        if (s1Len > s2Len) return false;

        int[] s1Count = new int[26];
        int[] s2Count = new int[26];
        
        for (int i = 0; i < s1Len; i++) {
            s1Count[s1.charAt(i) - 'a']++;
            s2Count[s2.charAt(i) - 'a']++;
        }
        
        for (int i = 0; i < s2Len - s1Len; i++) {
            if (Arrays.equals(s1Count, s2Count)) return true;
            s2Count[s2.charAt(i) - 'a']--;
            s2Count[s2.charAt(i + s1Len) - 'a']++;
        }
        
        return Arrays.equals(s1Count, s2Count);
    }
}

JavaScript solution

correspondant/original

var checkInclusion = function(s1, s2) {
    let s1Len = s1.length, s2Len = s2.length;
    if (s1Len > s2Len) return false;

    let s1Count = new Array(26).fill(0);
    let s2Count = new Array(26).fill(0);

    for (let i = 0; i < s1Len; i++) {
        s1Count[s1.charCodeAt(i) - 97]++;
        s2Count[s2.charCodeAt(i) - 97]++;
    }

    for (let i = 0; i < s2Len - s1Len; i++) {
        if (s1Count.toString() === s2Count.toString()) return true;
        s2Count[s2.charCodeAt(i) - 97]--;
        s2Count[s2.charCodeAt(i + s1Len) - 97]++;
    }

    return s1Count.toString() === s2Count.toString();
};

Python solution

correspondant/original

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        from collections import Counter
        
        s1Count = Counter(s1)
        s2Count = Counter(s2[:len(s1)])
        
        if s1Count == s2Count:
            return True
        
        for i in range(len(s1), len(s2)):
            s2Count[s2[i]] += 1
            s2Count[s2[i - len(s1)]] -= 1
            if s2Count[s2[i - len(s1)]] == 0:
                del s2Count[s2[i - len(s1)]]
            if s1Count == s2Count:
                return True
        
        return False

Go solution

correspondant/original

func checkInclusion(s1 string, s2 string) bool {
    s1Len, s2Len := len(s1), len(s2)
    if s1Len > s2Len {
        return false
    }

    s1Count, s2Count := make([]int, 26), make([]int, 26)
    for i := 0; i < s1Len; i++ {
        s1Count[s1[i]-'a']++
        s2Count[s2[i]-'a']++
    }

    for i := 0; i < s2Len-s1Len; i++ {
        if equal(s1Count, s2Count) {
            return true
        }
        s2Count[s2[i]-'a']--
        s2Count[s2[i+s1Len]-'a']++
    }

    return equal(s1Count, s2Count)
}

func equal(a, b []int) bool {
    for i := range a {
        if a[i] != b[i] {
            return false
        }
    }
    return true
}

Algorithm

Создать tableau для подсчета символов в строке s1. Затем создать аналогичный tableau для первых len(s1) символов строки s2.

Использовать скользящее окно для перемещения по строке s2. Для каждой позиции окна обновлять tableau подсчета символов и сравнивать его с tableauом для строки s1.

Если tableauы совпадают на любом этапе, вернуть true. Если окно достигает конца строки s2 и совпадений не найдено, вернуть false.

😎

Vacancies for this task

offres actives with overlapping task tags are affichés.

Toutes les offres

Il n'y a pas encore d'offres actives.