CODEKATA #33

すべての画像を検索

(ハッシュ、ダブルポインタ、スライドウィンドウ)

S文字列では、T文字列とSの部分文字列の個数を求めるプログラムを記述する.図を認識するときに大文字と小文字を区別します.一部の文字列は連続文字列でなければなりません.

私の答え

function compareMaps(map1, map2) {
  if (map1.size !== map2.size) return false;
  for (let [key, val] of map1) {
    let tmp = map2.get(key);
    if (tmp !== val || (tmp === undefined && !map2.has(key))) return false;
  }
  return true;
}
function solution(s, t) {
  let answer = 0;
  let sH = new Map();
  let tH = new Map();
  let i = 0;
  while (i < t.length) {
    if (tH.has(t[i])) tH.set(t[i], tH.get(t[i]) + 1);
    else tH.set(t[i], 1);
    if (sH.has(s[i])) sH.set(s[i], sH.get(s[i]) + 1);
    else sH.set(s[i], 1);
    i++;
  }
  if (compareMaps(sH, tH)) answer++;
  for (let idx = 0; idx < s.length; idx++) {
    let lt = s[idx];
    let rt = s[idx + t.length];
    if (sH.get(lt) === 1) sH.delete(lt);
    else sH.set(lt, sH.get(lt) - 1);
    if (sH.has(rt)) sH.set(rt, sH.get(rt) + 1);
    else sH.set(rt, 1);
    if (compareMaps(sH, tH)) answer++;
  }
  return answer;
}

let a = 'bacaAacba';
let b = 'abc';
console.log(solution(a, b));

正解を解く

function compareMaps(map1, map2){
  if(map1.size!==map2.size) return false;
  for(let [key, val] of map1){
    if(!map2.has(key) || map2.get(key)!==val) return false;
  }
  return true;
}
function solution(s, t){
  let answer=0;
  let tH = new Map();
  let sH = new Map();
  for(let x of t){
    if(tH.has(x)) tH.set(x, tH.get(x)+1);
    else tH.set(x, 1);
  }
  let len=t.length-1;
  for(let i=0; i<len; i++){
    if(sH.has(s[i])) sH.set(s[i], sH.get(s[i])+1);
    else sH.set(s[i], 1);
  }
  let lt=0;
  for(let rt=len; rt<s.length; rt++){
    if(sH.has(s[rt])) sH.set(s[rt], sH.get(s[rt])+1);
    else sH.set(s[rt], 1);
    if(compareMaps(sH, tH)) answer++;
    sH.set(s[lt], sH.get(s[lt])-1);
    if(sH.get(s[lt])===0) sH.delete(s[lt]);
    lt++;
  }
  return answer;
}

let a="bacaAacba";
let b="abc";
console.log(solution(a, b));

学識

答えは私の答えと似ています.念入りに実現された部分は、Map()間の比較関数compareMaps()である.まずMap.sizeを用いて各Mapの大きさ、すなわちkeyの個数が一致しているかを確認した.key個の数の比較を行うために、Map.sizeのkey毎のvalueが0の場合、Map.delete(key)により削除される.
その後、それぞれkey、valueを例に検証を行い、このkeyが比較対象Mapに存在するか否かを確認し、存在する場合、そのkeyのvalueが同一であるか否かを確認し、trueまたはfalseがreturnであるか否かを判断する.

改善すべき点

前述したように,解答中の演算回数は私の解答と同じであるが,コードの効率と可読性に差がある.私の解答は、最初のwindowサイズで検証する必要があるグラフと同じサイズを生成し、繰り返し文でスライドしました.したがって、スライドを行う前に、window関数を使用して、最初のcompareMaps()がarnagramであるかどうかを決定する必要があります.しかし解答では,アナック長より1つ短い文字列をMapと指定し,繰り返し文にrtを追加した後,それをcompareMaps()と比較し,ltを削除し,アナック長より1つ短い文字列を再生成した.次の図は、理解を助ける比較表です.