文字列のアナグラム

「abc」という文字列が与えられた場合、それが「adcba」という文字列のアナグラムであるかどうかを判断します。

この問題の直感的な解法は、二重ポインターを使用して解答することです。まず、s1 の各文字の数をマップに記録し、次に s2 を走査します。各走査のたびに、二重ポインターを開始し、start を現在の走査インデックス、end を start + s1.length に設定します。この範囲の文字列の長さは s1 と同じですので、マップリストを更新するだけです。二重ポインターが終了したとき、マップがすべて 0 であれば、s2 の部分文字列は s1 のアナグラムです。

以下の解法は、上記の解法と同じです。

// マップがすべて0であるかどうか
function everyZero(map){
  return Object.values(map).every(i => i===0)
}
function solve(s1, s2) {
  if(typeof s1 !== 'string' || typeof s2 !== 'string') return false
  if(s1.length > s2.length) return false
  const map = {};
  // s1を反復し、文字をキーとして文字の数を保持する
  s1.split('').map((i, index)=>{
    if(!map[i]) map[i] = 0
    map[i]++
    // s2の文字に出会った場合、減らす
    if(!map[s2[index]]) map[s2[index]] = 0
    map[s2[index]]--
  })
  // 先頭にアナグラムが存在するかどうかを判断する
  const bool = everyZero(map)
  if(bool) return bool
  
  let len = s1.length;
  // s2を反復し、新しい文字は減らし、古い文字は増やす
  // 以前に減らしたので、後で増やす。アナグラムが存在する場合、マップはすべて0になります
  for(let i = len; i < s2.length; i++){
    let val = s2[i];
    if(!map[val]) map[val] = 0
    map[val]--
    map[s2[i - len]]++

    const bool = everyZero(map)
    if(bool) return bool
  }
  return false
}