Блог

Я работаю над проблемой 438 с литкодом. Найдите все анаграммы в строке:

Учитывая две строки s и p , верните массив всех начальных индексов p анаграмм в s . Вы можете вернуть ответ в любом порядке.

s и p состоят из строчных английских букв.

Мой Подход

Я сохраняю частоту каждого символа в массиве и использую скользящее окно.

1. Использование объявления глобального массива

 let arr:number[]=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]; // outside any function
function check(arr1:number[],arr2:number[]):boolean{
    for (let i=0;i<26;i  ){
        if (arr1[i]!=arr2[i]){
            return false;
        }
    }
    return true;
}
function findAnagrams(s: string, p: string): number[] {
    let ans:number[]=[],
    lengthP:number=p.length,
    lengthS:number=s.length,
    j:number=0;
    if (lengthP>lengthS){
        return ans;
    }
    let arrP:number[]= [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];
    for (let chr of p){
        arrP[chr.charCodeAt(0)-97]  ;
    }
    for (let i=0;i<lengthP;i  ){
        arr[s[i].charCodeAt(0)-97]  ;
    }
    if (check(arr,arrP)){
        ans.push(0);
    }
    for (let i=lengthP;i<lengthS;i  ){
        arr[s[j].charCodeAt(0)-97]--;
        arr[s[i].charCodeAt(0)-97]  ;
        j  ;
        if (check(arr,arrP)){
            ans.push(j);
        }
    
    }
    return ans;
};
 

2. Использование объявления массива функциональных областей

 function check(arr1:number[],arr2:number[]):boolean{
    for (let i=0;i<26;i  ){
        if (arr1[i]!=arr2[i]){
            return false;
        }
    }
    return true;
}
function findAnagrams(s: string, p: string): number[] {
    let arr:number[]=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]; // inside function
    let ans:number[]=[],
    lengthP:number=p.length,
    lengthS:number=s.length,
    j:number=0;
    if (lengthP>lengthS){
        return ans;
    }
    let arrP:number[]= [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];
    for (let chr of p){
        arrP[chr.charCodeAt(0)-97]  ;
    }
    for (let i=0;i<lengthP;i  ){
        arr[s[i].charCodeAt(0)-97]  ;
    }
    if (check(arr,arrP)){
        ans.push(0);
    }
    for (let i=lengthP;i<lengthS;i  ){
        arr[s[j].charCodeAt(0)-97]--;
        arr[s[i].charCodeAt(0)-97]  ;
        j  ;
        if (check(arr,arrP)){
            ans.push(j);
        }
    
    }
    return ans;

};
 

Проблема

Первый из них дает неправильный ответ на некоторые тестовые примеры, но второй на 100% правильный.

Действительно ли это происходит из arr -за того, как объявлен путь?

Если да, то я что-то упускаю в локальном и глобальном объявлении в машинописном тексте?

• правильная подача
• неправильное представление

Проблема с использованием глобального массива заключается в том, что он будет сохраняться при нескольких вызовах findAnagrams . Таким образом, в то время как первый вызов даст правильный результат, второй вызов не начнется с заполнения нуля arr , а будет основываться на результатах предыдущего вызова, что, очевидно, приведет к неправильным подсчетам.

Это не связано конкретно с машинописным текстом-то же самое было бы и в обычном JavaScript.

Вы могли бы исправить первую версию, сбросив значения arr в начале findAnagrams :

 arr.fill(0);
 

Но в любом случае лучше сохранять такую переменную в локальной области.