438. Find All Anagrams in a String Javascript

⚡문제정보

Anagram이 성립하는 경우를 체크하면 되는 문제인데

시작인덱스부터 p의 길이만큼 비교해보고 성립하면 그 시작인덱스를 체크하면되는 문제입니다.

모든 시작점을 다 체크해봐야겠네요

---

🔍나의 첫번째 풀이

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    s = s.split('')
    p = p.split('')
    let map = new Map()
    let answer = []
    let set = new Set(p)
    for( string of p){
        map.set(string, (map.get(string)||0) + 1 )
    }
    
    
    for(i=0 ; i <= s.length - p.length; i++) {
        let dumap = new Map(map)
        let sl = s.slice(i, i+p.length)
        for(j=0 ; j<sl.length; j++) {
            if(!set.has(sl[j])) break
            dumap.set(sl[j], dumap.get(sl[j]) -1 )
            if( 0 > dumap.get(sl[j])) break
        }
        let flag = [...dumap.values()].filter(ele => ele != 0 )
        if(!flag.length) answer.push(i)
    };
    return answer
};

정답은 반환되었지만 런타임이 하위 5%였습니다.

아무래도 매번 slice하는 방식이 매우 비효율적인것 같고

아나그램은 일반적으로 한개의 글자만 사용된다하니

slice를 빼고 map도 없애보면 더 빠르지않을까 해서 새로 코드를 짰습니다.

---

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    s = s.split('')
    p = p.split('')
    let len = s.length - p.length
    let dp = new Array(len).fill(null)
    let set = new Set(p)
    
    for(i=0 ; i <= len; i++) {
        let inset = new Set()
        let flag = true
        for(j = 0 ; j < p.length; j++ ) {
            if(!set.has(s[i+j])) {
                flag = false
                break
            }
            if(inset.has(s[i+j])) {
                flag = false
                break
            }
            inset.add(s[i+j])
        }
        if(flag) dp[i] = i
    };
    return dp.filter(ele => ele != null)
};

이렇게했더니 baa , aa 케이스에서 오류가나네요

아니 아나그램은 같은 알파벳 안나온다며요

하지만 dp를 사용하는건 꽤 괜찮을 것 같습니다.

---

🔍새로 푼 풀이

 

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    s = s.split('')
    p = p.split('')
    let len = s.length - p.length
    let a = Math.max(s.length , p.length)
    let dp = new Array(a).fill(null)
    let set = new Set(p)
    let map = new Map()
    for( string of p){
        map.set(string, (map.get(string)||0) + 1 )
    }

    for(i=0 ; i <= len; i++) {
        let flag = true
        let dumap = new Map(map)
        for(j=0; j<p.length; j++) {
            if(!set.has(s[i+j])) {
                flag = false
                break
            }
            dumap.set(s[i+j] , dumap.get( s[i+j]) - 1)
            if( 0 > dumap.get(s[i+j])) {
                flag = false
                break
            }
        }
        if(flag) dp[i] = i
    };
    return dp.filter(ele => ele != null)
};

근데 런타임은 그대론데 dp를 사용하느라 메모리 사용량만 더 늘어난 코드가 되어버렸습니다.

아니 다른 사람들은 어케 짰길래 그렇게 빠른거임?

---

🔍런타임이 제일 빠른 다른사람 풀이

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
const foo = (arr1, arr2)=>{
  for(let i = 0; i<arr1.length;i++)
    if(arr1[i] !== arr2[i]) return false
  return true
}

var findAnagrams = function(s, p) {
    let sArr = new Array(26).fill(0)
    let pArr = new Array(26).fill(0)
    let res = []
        
    for(let i =0; i<p.length; i++){
        let index = p.charCodeAt(i)%26;
        pArr[index]++
    }
    
    for(let i = 0; i<s.length;i++){
        let index = s.charCodeAt(i)%26;
        sArr[index]++;
        
        if(i>p.length-1){
          let headIndex = s.charCodeAt(i-p.length)%26
          sArr[headIndex]--
        }
        if(i>=p.length-1){
          if(foo(sArr, pArr)) res.push(i-(p.length-1))
        }
    }

    return res
};

charcodeAt을 이용해서 많이 풀었네요

아니 이게 뭐임

애초에 전 접근부터가 틀려먹었군요..