[leetcode] 438. Find All Anagrams in a String

문제링크

https://leetcode.com/problems/find-all-anagrams-in-a-string/

input & output

Example 1

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]

• Explanation:
  The substring with start index = 0 is "cba", which is an anagram of "abc".
  The substring with start index = 6 is "bac", which is an anagram of "abc".`

Example 2

Input: s = "abab", p = "ab"
Output: [0,1,2]

• Explanation:
  The substring with start index = 0 is "ab", which is an anagram of "ab".
  The substring with start index = 1 is "ba", which is an anagram of "ab".
  The substring with start index = 2 is "ab", which is an anagram of "ab".`

---

Approach #1

/*
a:1 b:1 c:1

1
0123456789
cbaebabacd
^
   ^
*/

Solution #1

// time: O(2N) -> 맨끝문자가 anagram일때
// space: O(P)
var findAnagrams = function(s, p) {
    let res = [];
    //edge case
    if(p.length>s.length) return res;
    
    //p로 map 만든다.
    let map = new Map();
    for(let c of p){
        map.set(c, (map.get(c) || 0) +1);
    }
    //console.log(map)
    let left=0, right=0;
    let counter = map.size;
    //a:0 b:1 c:0
    //cbaebabacd 1
    //      ^
    //         ^
    //0,
    while(right < s.length){
        //console.log(left, right, counter)
        //console.log(map)
        let curChar = s.charAt(right);
        if(map.has(curChar)){
            map.set(curChar, map.get(curChar)-1);
            if(map.get(curChar)===0) counter--;
        }
        right++;
        while(counter === 0){
            let leftChar = s.charAt(left);
            if(map.has(leftChar)){
                map.set(leftChar, map.get(leftChar)+1);
                if(map.get(leftChar)>0) counter++;
            }
            if(right-left === p.length){
                res.push(left);
            }
            left++;
        }
    }
    return res;
};

Time Complexity

O(2N)->O(N)

N: string s의 길이
worst case: 맨 끝의 문자를 포함해야 anagram이 되는 경우, while문 안에서 left, right를 증가시키며 최종적으로 문자 확인을 2*N번 만큼 하게된다.

Space Complexity

O(P)

P: string p의 길이
map의 크기는 p의 길이만큼이기 때문.

---

Solution #2

// time: O(P^2)
// space: O(2*P)
var findAnagrams = function(s, p) {
    const result=[];
    const map = createMap(p); //O(P)
    let i=0;
    //cbacbabacd
    //        ^
    //a:0 b:1 c:0
    //potential: 7 / result: 0,1,2,3,6
    while(i<=s.length-p.length){ // O(S-P)
        let potential=i;
        let copy = copyMap(map); // O(P)
        
        for(let j=0;j<p.length;j++){ //O(P)
            let cur=s[i+j];
            if(copy.get(cur)>0) copy.set(cur,copy.get(cur)-1);
            else break;
            if(j===p.length-1) result.push(potential);
        }
        i+=1;
    }
    return result;
};

function copyMap(map){
    const copy = new Map();
    
    for(let [key,value] of map){
            copy.set(key,value);
    }
    
    return copy;
}
function createMap(p){
    const map = new Map();
    
    for(let c of p ){
        if(map.has(c)) map.set(c,map.get(c)+1);
        else map.set(c,1);
    }
    
    return map;
}

Time Complexity

O(P^2)

while문 을 돌며 map에 현재 문자가 있는지 확인하는데, p의 길이만큼의 문자열을 확인하기 때문에 대략적인 시간복잡도는 P*P가 될것.

Space Complexity

O(2P)->O(P)

p의 길이만큼 map이 생성될 것이고, 그 map을 copy해서 사용하기 때문에 공간복잡도는 2*P.

---