JavaScriptでLeetCodeを始めました~Strings編~[前編]

leetcode プログラミング

前回でArray編を完了しました！
なので、今週からは2回にわけてStrings編に取り組んでいこうと思います！ちなみにLeetCodeの方は現在この一つ先であるLinkedListに取り組み始めました。こちらは普段の業務でなかなか実装することがないため、模索しながらの実装を進めています。

また、本日初めてLeetCodeのContestに参加しました！
初めての参加で問題の意図がつかめない部分もあったりしたのですが、なんとか第1問と第3問は回答することができました。 第3問については、このブログを通して身につけた正規表現とバイナリサーチで回答できたので成長を実感できました！😄やっぱり前はできなかったことができるようになると嬉しいですね！
というわけで、今週もLeetCodeに取り組んだ内容についてまとめたいと思います！

Reverse String

これはめちゃくちゃ簡単な内容ですね。「配列で渡された内容をin-placeで反転させる」だけです。
JavaScriptでは、配列をin-placeで反転されるreverseという関数があるので、これは以下のようにシンプルな実装となります。

/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
const reverseString = function (s) {
  s.reverse();
};

ただこれだと味気ないので、一から実装すると以下のようになります。

const reverseString = function (s) {
  let temp = "";
  const len = Math.floor(s.length / 2);
  for (let index = 0; index < len; index++) {
    temp = s[index];
    s[index] = s[s.length - 1 - index];
    s[s.length - 1 - index] = temp;
  }
};

よくあるswapアルゴリズムと一緒ですね。
一旦、一方の値を退避させて片方の値を他方に入れ、もう一方に退避させていた値を代入するという奴です。
ただ、敢えて実装してもスピードもメモリ消費量も改善しないので、reverse 関数を用いるのが賢いと思います😅

Reverse Integer

前述のReverse StringsのIntegerバージョンですね。
ただ数字を扱うため、

  1. -のような符号を気にする必要があるため単純にreverseで完結しない
  2. 32bit符号付き整数を超える値の時は0を返す

を処理するための一手間が必要になります。

以上を踏まえた実装が以下になります。

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function (x) {
  const str = x.toString();
  if (str[0] === "-") {
    x = "-" + str.split("").slice(1, str.length).reverse().join("");
  } else {
    x = str.split("").reverse().join("");
  }
  if (x > Math.pow(2, 31) || Math.pow(-2, 31) > x) {
    return 0;
  } else {
    return Number(x);
  }
};

まず一文字目に着目し、負の値か否かを確認します。負の値であれば最初の文字以外を配列化してから反転させ、文字列にします。正の値であれば、全ての文字で同じ処理を行います。また、その後32bit符号付き整数かどうかを確認して、32bitを超える値の場合は0を返します。ただ、上記ではなかなかスピードが出ませんでした…😅
そこで、他の回答例を参考にしたところ下記は考え方は同じなのですが、全体的にコードをシンプルにすることでパフォーマンスに若干の改善が見られましたので追記しておきます。

/**
 * @param {number} x
 * @return {number}
 */
const reverse = (x) => {
  let first = "";
  const str = x.toString().split("");
  if (x < 0) {
    first = str.shift();
  }
  x = str.reverse().join("");

  if (x > Math.pow(2, 31)) return 0;

  return first + x;
};

First Unique Character in a String

問題内容は、「文字列の中から他の要素と重複しない単一のものを選び、その中でも一番最初に現れるものについて、そのインデックスを答えよ」という内容です。
方針としては、文字列の最初から順番に確認していき、その文字列が以降に含まれないのであれば、そのインデックスを返す。そして、仮に含まれるのであればHashMapに入れてしまい後々のチェックを軽くするという方針を取りました。それを踏まえた実装が以下になります。

/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function (s) {
  const map = new Map();
  for (let index = 0; index < s.length; index++) {
    if (map.has(s[index])) continue;
    if (!s.slice(index + 1, s.length).includes(s[index])) {
      return index;
    }
    map.set(s[index]);
  }
  return -1;
};

パフォーマンス的にはまあまあといったところでしょうか。
ただせっかく文字列がテーマなので正規表現を使いたいと思い実装したのが次になります。

/**
 * @param {string} s
 * @return {number}
 */

var firstUniqChar = function (s) {
  if (s === "") return -1;
  const reg = s
    .split("")
    .sort()
    .join("")
    .match(/(.)\1{0,}/g)
    .filter((item) => item.length === 1)
    .map((item) => s.indexOf(item));
  return reg.length > 0 ? Math.min(...reg) : -1;
};

まず与えられた文字列が何もなければ-1を返します。そして、その後文字列を配列化してソートをかけます。すると、文字列が昇順になるため、仮に重複があれば連続するようになります。ここに「0以上で同じ文字列が連続しているもの」という正規表現をかけることで、同じ文字が連続しているもの(=重複しているもの)としていないもの(=単一のもの)を配列として分けることができます。同じ文字が複数あるものはその後、filterにより除去できます。そして、単一の文字だけにした後に、それらの順番をindexOfで取得した配列を作ります。最後に、この配列の長さが0であれば単一の文字は無かったということで-1が返り、そうでなければ最小のインデックスを返すということで答えが出せます。個人的には、結構スマートな解法ではないかと思うのですが、パフォーマンスは全然悪いです。最初の解法の2倍時間がかかっています。なので、実務ではあまり好ましくないですね。

最後に、提出後に他の解法を確認し、スマートだなと思ったやり方を紹介します。

/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function (s) {
  if (s.length == 0) return -1;
  for (let index = 0; index < s.length; index++) {
    if (s.indexOf(s[index]) === s.lastIndexOf(s[index])) return index;
  }
  return -1;
};

こちらは順番に文字を確認していくのですが、indexOf(該当する値の最初に出てくるインデックスを返す)とlastIndexOf(該当する値の最後のインデックスを返す)を用いています。確かにこの2つの関数の返り値が等しいということは、すなわち単一の値ということなので、正しい答えになります。また記述量も少なくパフォーマンスも抜群です。自分にはちょっと思いつかなかったので、この解法を導けるのは凄いなと感心しました。

Valid Anagram

「2つの文字列が渡される。一方の文字列が他方の文字列のアナグラムであるか否かを判定せよ」という問題です。
これは当初ブルートフォースで考えていました😅しかし、アルゴリズムが複雑になりますし、計算量も文字列の長さだけ増えていく。これは全然スマートじゃないと考え、途中で止めました。そこで再考したところ、アナグラムは順番を入れ替えて同じになる文字列。すなわち一方の文字列と他方の文字列は順番だけが異なるのだから、順番を揃えれば同じ文字列になるはず！と気付き、以下のような回答を作りました。

var isAnagram = function (s, t) {
  const origin = s.split("").sort().join("");
  const target = t.split("").sort().join("");
  if (origin === target) {
    return true;
  } else {
    return false;
  }
};

パフォーマンスはそこそこですが、解法的には文字列としての特徴を掴んだシンプルで良い解法ではないかと思います。 この問題に関してはこれで満足したので、この解法のみです。

Valid Palindrome

「ある文字列が渡される。その文字列が回文か否かを判定せよ」という問題ですね。 回文であるならば、シンプルにstr === str.reverseあたりで解決したくなるのですが、この問題のいやらしいところは記号や空白が含まれているところです。なので、それらのノイズを省いて純粋な文字列として回文を判定する必要があります。
ここで活躍するのが正規表現です。

developer.mozilla.org

ちなみに自分は正規表現が苦手です。仕事はフロントエンドなのですが、あんまり使う機会がないため経験不足なことが理由です。
ただ今回の問題は正規表現を用いればスマートに解けると考え、正規表現を調べました。そして、以下のような解法を導きました。

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function (s) {
  const str = s.toLocaleLowerCase().match(/[a-z]|[0-9]/g);
  if (str === null) {
    return true;
  }
  if (str.join("") === str.reverse().join("")) {
    return true;
  } else {
    return false;
  }
};

文字列をまず小文字に揃えて、その後正規表現で文字と数字だけにフィルタリングしたものを作ります。そして、それが存在しければtrueを返します。(文字が存在しない = 空白文字と捉えれば空白文字の回文であるため)もし文字が存在すれば、matchの返り値である配列が文字列として逆さまにした時も同じ文字列であるか確認し、同じならばtrue、異なればfalseを返します。
正規表現には苦手意識があったこともあり、MDNを睨めながらなんとかかんとか解いた問題ですが、終わった後には以前よりも親しみを感じるようになりました。何事も経験することが大事ですね！

まとめ

Stringsに入ってみたのですが、JavaScriptではcharがなくstringのみであり、stringも配列のように扱える関数が結構あることから前回のArrayに近い感覚でやれています。これが良いことなのか悪いことなのかは定かではありませんが…😅
ただ、解法としてパフォーマンスを意識すると今回の例のように正規表現を使ったり冒頭で述べたバイナリサーチによる文字列検索を行う場面が生まれ、そこはArrayとは違った角度で吸収できる武器になっているので嬉しく思います！まだまだEasy問題なのでひよっこも同然ですが、一歩ずつアルゴリズムを学習し、実際に活用する経験を踏んで成長していきたいと思います。
元々面倒くさがり屋なのでブログに対するモチベーションが萎えそうになったりもしますが、このようにアウトプットすることで得られる成長を糧として次回も頑張ってStrings後編をまとめたいと思います！✌️