JavaScriptでLeetCodeを始めました~Strings編~[後編] - ムスリムエンジニアbebetaroのブログ

一週間ぶりのブログ更新です！
前回まで取り組んだLeetCode Top Interview QuestionsのStrings編後編をまとめたいと思います！
最近、LeetCodeやってて気づいたのですが、いつの間にかTypeScriptが追加されていますね！個人的には、TypeScriptの方がVSCodeで補完が効くので好みです！現在取り組んでいるTreesからTypeScriptで書いているので、この後に続くLinkedList以降はタイトルが「TypeScriptでLeetCode始めました」になると思います。それはさておき、後編を以下にまとめていきます！

String to Integer (atoi)
Implement strStr()
Count and Say
Longest Common Prefix
まとめ

String to Integer (atoi)

「渡された文字列から空白や数字以外を排して、数字のみを返しなさい。ただし、渡された文字列が空の場合や最初の文字が数字以外の場合は0を返しなさい」という問題です。まず、この問題は正規表現が得意であれば簡単に解けると思います。ただ、自分は前回の記事でもお話したように正規表現が得意ではないので、いくつか処理を分けて行っており冗長になっています。また、もっとスマートな解法もあると思いますが、本問題はLeetCodeの問題ページに解法がありませんので、ひとまず自分としてはこのように解いたという感じで紹介します。

/**
 * @param {string} str
 * @return {number}
 */
var myAtoi = function (str) {
  str = str.trim().split(" ")[0];
  // 数式を含んでいないケースを排除している
  if (!/\d/.test(str)) {
    return 0;
  }

  // 先頭以外の'+'または'-'を排除している
  // '.'は小数点を含んだ数字のために取り込んでいる
  const num = str.match(/^-|^\+|\.|\d*/g);
  let ans = num[0] + num[1];

  if (isNaN(ans) || num[0] === "") {
    return 0;
  }
  // 符号付き32bit整数以上となる値は、符号付き32bitの最大数あるいは最小値を返す
  if (Math.abs(ans) > Math.pow(2, 31) - 1) {
    return ans > 0 ? Math.pow(2, 31) - 1 : Math.pow(-2, 31);
  } else {
    return ans;
  }
};

コメントアウトしてある処理の通りなのですが、まずは与えられた文字列の前後の空白をtrim関数により無くします。そして、一旦文字列を空白文字で区切った配列にして最初以外の文字はここで無くします。これは本問題が、最初の非空白文字列のみを対象とするため、それ以降の非空白文字列に価値はないからです。その後、もしその一番最初の非空白文字列が数字を含んでいなければ、ここで0を返します。

次に正と負を表す+と-に着目します。これらの記号が数字に続いていればよいのですが、+-2や222-222など先頭以外に含まれていた場合、それは排除しなければありません。なので、続く正規表現では①先頭時に+あるいは-を含む、また.は小数点を表す時に必要なのでそれも含む数字の文字列としています。正規表現のmatch関数により配列となったこの文字列ですが、先の正規表現により弾かれた部分は空白となっています。ここで次のようなパターンが考えられます。

先頭が+あるいは-であり、数字が続いてる場合(['+', '123', ' ',...]のようなケース)
先頭に符号がない数字の場合(['123', ' ', ...]のようなケース)
先頭に.がきたり、先頭の符号の後にまた符号が来て2つ目の要素が空欄が来て数字ではなくなっているケース([' ', '1', ...])

ここでまとめて考えると、この数字の判定にはいずれも配列の先頭2つしか必要ないとわかります。
なぜならば、1の場合は1つ目が符号であり2つ目が数字で、それ以降は(空白 = 非数字)を挟んでいるため数字には含みません。2つ目の場合も1つ目の数字だけしか必要ありませんが、2つ目の空白を含んだとしても数字には影響しません。また、3つ目の要素以降に数字を含んでいたとしても、それは非数字を挟んでいるため答えの数字にはカウントしません。なので、2つ目まででジャッジができるのです。
最後の3つ目だけは少し考慮する必要がありまして、例えば+-2のように先頭に符号文字が続いた場合、正規表現でを経て先頭2つを取り出すと、['+', ' ']となります。この2つを合わせると文字列の+となります。これは数字で考えるとNaNとなるため、isNaNでジャッジすると弾けます。また、.1のような先頭に符号以外を含んだ数字の場合ですが、これは上記のmatchに通すと[' ', '1']となります。したがって、配列の先頭が空白文字となっている答えは自ずと非数字文字とわかります。以上、3つ目のケースをif文で0を返すようにすることで、ans変数には純粋な数字のみが残ります。最後に、ans変数が32bit符号付き整数の上限あるいは下限を超えるとき、それぞれの最大値(最小値)を返せば、答えが導けます。結構、正規表現で考える場面が多く、骨が折れましたが同時にとても勉強になる問題でした！😄

Implement strStr()

「ある文字列が2つ与えられる。一方が他方の文字列の一部である時、その文字列の出てくる順番を返せ。また含まない時は-1を返せ」という問題です。
これはJavaScriptに標準関数であるindexOfを使うと一瞬で解けてしまいますね😅以下のような解法になります。

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function (haystack, needle) {
  const len = needle.length;
  for (let index = len - 1; index < haystack.length; index++) {
    let ans = "";
    if (
      haystack[index] === needle[len - 1] &&
      haystack[index - (len - 1)] === needle[0]
    ) {
      for (let j = 0; j < len; j++) {
        ans += haystack[index - (len - 1) + j];
      }
    }
    if (ans === needle) {
      return index - (len - 1);
    }
  }
  return -1;
};

ほぼほぼブルートフォースで一緒ですね。for文を回して、haystackの一部について、先頭と終わりをneedleと比較して、もし先頭と最後が一緒の文字である場合、中身を精査しています。ただし一部違う点としまして、for文の開始をneedleの長さ分調整しています。こうすることで、needleの先頭と最後の文字が一致するパターンを見つけることがfor文で容易にできます。これは、index = 0からスタートだとlen-1分を足して任意にfor文を終わらせる必要があるが、len-1スタートだとfor文の終わりまで何も考えずに回せるからです。
また、if (haystack[index] === needle[len - 1] &&haystack[index - (len - 1)] === needle[0])で一致した後、その後の要素を一つずつ確認してもしneedleと異なれば次のループというパターンも考えたのですが、実際に実装してもパフォーマンス上の優位が見られず、むしろいちいちif文で確認するほうがパフォーマンスに影響しそうだったので省きました。ただここらへんはもう少しスマートにできそうなポイントだと思っていますが、一方でパフォーマンスで考えるとindexOfを使うのが最もスマートなので、ここはこれでいいかなとも思っています😅

Count and Say

「Count and Say(別名: Look and Say)数列を実装せよ」という問題です。最初はマジで何のこっちゃ？？ってなりました。Count and Say数列について知りませんでしたので。ただ調べてみますと、その前の数列に応じて次の数列を作るパターンのようですね。口頭で自分が説明するのは難しいので、詳しくはこちらのページを見ていただけますと分かりやすいです。

mathtrain.jp

そのCount and Sayですが、自分は次のように実装しました。

/**
 * @param {number} n
 * @return {string}
 */
var countAndSay = function (n) {
  if (n === 1) return "1";
  let ans = "1";
  for (let index = 0; index < n - 1; index++) {
    ans = generateString(ans);
  }
  return ans;
};

/**
 * @param {string} num
 * @return {string}
 */
const generateString = (num) => {
  let ans = "";
  let temp = num[0];
  for (let index = 1; index < num.length; index++) {
    if (num[index] !== num[index - 1]) {
      ans += `${temp.length}${num[index - 1]}`;
      temp = num[index];
    } else {
      temp += num[index];
    }
  }
  ans += `${temp.length}${temp[0]}`;

  return ans;
};

実装としては、解を作り出すgenerateStringという関数を作り、for文を与えられた数字分回して、最終的な答えを導き出すという感じです。それでは肝心のgenerateStringの中身ですが、まず答えを入れるためのans変数と途中経過用のtemp変数を用意します。同時にtempには引数であるnumの最初の文字を入れます。その後、for文を回します。for文は、index = 1でスタートして、1つ前の値と比較します。もし1つ前の数字と今回の数字が異なれば、tempの長さと1つ前の値を合わせたものをansに代入します。また、tempには今回の値を新たに入れます。
もし今回の値と前回の値が同じであれば、tempにその値を新たに代入して、tempの長さを伸ばしていきます。最後に、for文を抜けた時は、tempには代入されていない値が残っているので、それを最後にansに渡して返り値とします。この繰り返しで、Count and Sayが求まります！

上記の解法がスタンダードであり、そこそこのパフォーマンスが出るのですが、他の解法を参照してみると正規表現を用いたスマートなものがあったので紹介したいと思います。

var countAndSay = function (n) {
  if (n === 1) return "1";

  return (
    countAndSay(n - 1)
      // n <= 30まででは同じ数字が3桁以上にならないので、正規表現で配列家できる
      .match(/1+|2+|3+/g)
      // reduceで各配列の長さと値を足していっている
      .reduce((acc, nums) => (acc += `${nums.length}${nums[0]}`), "")
  );
};

今回のCount and Sayでは代入される数字がn >= 30までです。ここまでの数字では、3以上の数字が出てくることはありません。なので、「１の連続した数字」、「２の連続した数字」、「３の連続した数字」のパターンで正規表現を用いれば求めたい形ごとに配列となりますので、あとは上記のようにreduceをかければスマートに答えを導くことが出来ます。再帰関数を用いている点もスマートでいいですね！パフォーマンスは自分の解法とどっこいですが、このようなスマートな解法を書けると格好いいので自分もこの境地に早く達したいです！☺️

Longest Common Prefix

「文字列の配列が与えられる。各文字列が共通して持つ最長のprefixを求めよ」という問題ですね。["flower","flow","flight"]であればflが最長のprefixとなります。ポイントは全ての文字列は答えとなるprefixを必ず持っているという点です。これを踏まえまして、自分は以下のように解きました！

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function (strs) {
  if (strs.length === 0) {
    return "";
  }
  const target = strs[0];
  let ans = "";
  for (let index = 0; index < target.length; index++) {
    let len = 0;
    for (let j = 1; j < strs.length; j++) {
      if (target[index] === strs[j][index]) {
        len++;
      }
    }
    if (len === strs.length - 1) {
      ans += target[index];
    } else {
      break;
    }
  }

  return ans;
};

まず、与えられた配列の一番最初の文字列をtargetという変数で持ちます。そして、同時に答えのprefixを入れていく、ans変数も用意します。あとは、targetを走査して一文字ずつ他の配列の文字列と比較していきます。この時、他の配列と同じ位置に同じ値があればlen変数を１つずつインクリメントしていきます。そして、ある文字の比較が終わった時にif (len === strs.length - 1)を行います。この時、lenと与えられた配列の長さ-1(targetを抜いているため)が等しいということは、全てに同じ値が含まれているということなので、ansにその値を追加します。これをlenが配列の長さと合わなくなるまで続けると、ansが導けます。

自分はこれで答えが出せました。 LeetCodeのSolutionを見ると、これと同じやり方がありまして、自分のやり方はVerical Scanningというらしいです。垂直的に値を比較していっているので納得ですね！また、Solutionには他の解法も載っていましたので、紹介したいと思います！

// Divide and Conquer
/**
 * @param {string[]} strs
 * @return {string}
 */
const longestCommonPrefix = (strs) => {
  if (strs.length === 0) return "";
  return _longestCommonPrefix(strs, 0, strs.length - 1);
};

/**
 * @param {string} left
 * @param {string} right
 * @return {string}
 */
const commonPrefix = (left, right) => {
  // 2つの文字列を比較して共通する文字列を返す
  const min = Math.min(left.length, right.length);
  for (let index = 0; index < min; index++) {
    if (left[index] !== right[index]) {
      return left.substring(0, index);
    }
  }
  return left.substring(0, min);
};

/**
 * @param {string[]} strs
 * @param {number} left
 * @param {number} right
 * @return {string}
 */

const _longestCommonPrefix = (strs, left, right) => {
  // 同じ位置を表すのであれば、それを返す
  if (left === right) {
    return strs[left];
  } else {
    // 真ん中で分けて、それぞれの共通項からさらに共通部分を求める
    const mid = Math.floor((left + right) / 2);
    const lcpLeft = _longestCommonPrefix(strs, left, mid);
    const lcpRight = _longestCommonPrefix(strs, mid + 1, right);
    return commonPrefix(lcpLeft, lcpRight);
  }
};

まずDivide and Conquerです。この解放長いし複雑です…。個人的にはあんまり好きじゃないです😅 導き方としては、配列を再帰的に半分に分けていきます。そして、それぞれからprefixを導き出していき、導き出したprefixから更にprefixを導き出すといった感じです。解法としては面白いアプローチですし、substring関数めっちゃ便利やなって思いました！ただ記述量がどうしても増えるのとアルゴリズムが複雑化してエラーが起きやすいこと、そしてその割にパフォーマンス的に優位性がないことからあんまり使うことは無いかなーという気もします。

// binary tree

/**
 * @param {string[]} strs
 * @return {string}
 */

const longestCommonPrefix = (strs) => {
  if (strs.length === 0) return "";
  let minLen = Number.MAX_SAFE_INTEGER;
  for (let index = 0; index < strs.length; index++) {
    // strsの中で最も短い文字列の長さを入れている
    minLen = Math.min(minLen, strs[index].length);
  }
  let low = 1;
  let high = minLen; // 一番短い文字列の長さを入れる
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    // isCommonPrefixが上手く行けばlowはmidの+1
    // 逆ならばhightがmid-1
    // すなわち上手く行っている場合は、midまでは含まれることが保証されているのでそれ以下の文字列は気にしなくていい
    // したがって、lowはmidに+1した値で考える
    // 一方失敗した場合は、それ以上の部分は求める意味がない。すなわち、mid以上は無意味となり、highはmid-1となる
    if (isCommonPrefix(strs, mid)) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  // lowは常に成功した値で更新されている。highがその値を下回る、あるいは同じ時、
  // highは成功した値として限界値であるので、highまでの長さで抜き出す
  return strs[0].substring(0, high);
};

/**
 * @param {string[]} strs
 * @param {number} len
 * @return {boolean}
 */

const isCommonPrefix = (strs, len) => {
  // 配列の最初の文字列について、入れた長さでsubstringする
  // subで全て行ければtrue, 失敗したらfalse
  const sub = strs[0].substring(0, len);
  for (let index = 1; index < strs.length; index++) {
    if (!strs[index].startsWith(sub)) {
      return false;
    }
  }
  return true;
};

個人的にはこっちの方が実践的な有用性は高いと思います。
コメントに書いてありますが、まず配列の中で最も短い文字列を見つけ、その長さをminLenに入れます。そして、最も短い長さlowを1、最も長い長さhighをminLenとします。(最長のprefixは最も短い文字列の全長になりうるため)
その後、whileループをhight>=lowの条件で回します。ループの中では、lowとhightの中間となる数字をmidとし、そのmidの数字でprefixを求められるかisCommonPrefix関数で求めます。もしisCommonPrefixが求められた時は、成功した = もっと大きな数字が答えとなりうると考え、lowにmid+1を代入します。すなわち検索対象が先程は1からだったものが、midからと半分になるのです。逆に失敗したならば、highがmid-1となります。すなわちこちらも検索対象がminLenからmidまでに半分となります。これを繰り返すことで検索範囲を狭めていき、最終的にはhighに答えとなるprefixの長さが入ります。これがbinary treeです。個人的にはbinary treeは先週のLeetCode Contestに早速応用できたので、便利だなっと感じました。またアルゴリズム的にもDivide and Conquerより読みやすいです。ただ、これに関しては個人差もあるのであくまで自分の意見となります😊

まとめ

今回でStringsが終わりました！Arrayに続いて勉強になるケースが多く、パフォーマンス改善や正規表現などフロントエンドエンジニアとしても仕事にも活きる場面が多く想像できます！LeetCodeに挑戦するのは時々大変ですが、多くの場合はパズルのようで面白いです！また、ただ面白いだけではなく、挑戦で得た経験や経験は仕事にも活きます。これがプログラミング学習の醍醐味ですね！😄
さて、来週からはLinkedListです！一応LinkedListは一通り既に終わっているのですが、これも面白かったです。フロントエンドで活きるケースとしては、パンくずあたりの管理ですかね？Arrayよりも柔軟性は損なわれますが、追加したり繋げる先を変えたりといった操作については利便性を感じました。詳しくは、来週も頑張ってまとめていきたいと思いますので、よろしくお願いします！