はじめに

Qiitaの競技プログラミング研究月間ということで、アルゴリズムの記事を書いています。
今回は文字列に関する問題をまとめました。

JavaScriptでアルゴリズムの勉強をされている方の参考になれば幸いです。
記事を順次まとめていきますので、その他の記事についてはマイページからご覧ください。

頭文字の大文字化

引数に文字列を与えたとき、各単語の頭文字だけ大文字にして返してください。

   capitalize('a short sentence') --> 'A Short Sentence'
   capitalize('a lazy fox') --> 'A Lazy Fox'
   capitalize('look, it is working!') --> 'Look, It Is Working!'

解答

以下の処理を考えます。

空配列wordsをつくる
引数の文字列をスペース区切りで配列にする
配列の各要素wordにforをまわす
- wordの先頭を大文字にする
- 先頭の大文字と残りの文字列連結する
- 連結した文字を配列wordsに格納する
配列wordsを文字列にして返す

index.js

function capitalize(str) {
  const words = [];

  // str.split(' ')でスペース区切りの配列をつくる
  for (let word of str.split(' ')) {
    words.push(word[0].toUpperCase() + word.slice(1));
  }

  return words.join(' ');
}

出現最多文字(MaxChars)

文字列を引数に与えたときに、一番現れる回数が多い文字を返してください。

 maxChar("abcccccccd") === "c"
 maxChar("apple 1231111") === "1"

解答

文字列の文字をキー、文字の出現回数を値にもつオブジェクト(連想配列)を作成します。

空のオブジェクトcharMapを用意し、for (let char of str)の中でcharをキーにしたオブジェクトを作成します。
文字が初出現したときはcharMap[char] = 1をセットし、2回目以降の出現ではcharMap[char]++のようにインクリメントしていきます。

オブジェクトを作成したら、各文字(キー)の出現回数とmaxを比較していき、maxより大きい値がでたらmaxを更新していきます。
また、maxの文字をmaxCharとして更新していき、更新結果を最後に返します。

index.js

function maxChar(str) {
  const charMap = {};

  let max = 0;
  let maxChar = '';

  // オブジェクト(文字: 出現回数)の作成
  for (let char of str) {
    if (charMap[char]) {
      charMap[char]++;
    } else {
      charMap[char] = 1;
    }
  }

  // 出現回数が多い文字が現れたら更新
  for (let char in charMap) {
    if (charMap[char] > max) {
      max = charMap[char];
      maxChar = char;
    }
  }

  return maxChar;
}

アナグラム

2つの文字列を引数として与えたときに、各文字列がアナグラム(同じ文字を同じ個数含んでいる)になっているかどうかを判定してください。
アナグラムは文字のみを考えます(記号については考えません)。
また、大文字・小文字の区別も行いません。

   anagrams('rail safety', 'fairy tales') --> True
   anagrams('RAIL! SAFETY!', 'fairy tales') --> True
   anagrams('Hi there', 'Bye there') --> False

解答

出現最多文字(MaxChars)のときと同様に、引数の2つの文字列をbuildCharMap()でオブジェクト(文字: 出現回数)に変換します。
オブジェクトを作成する際に、正規表現str.replace(/[^\w]/g, '')とtoLowerCase()を使うことですべての半角英数字とアンダースコアに含まれない一文字をすべて''に置き換え、文字列の文字をすべて小文字にしています。

if (Object.keys(aCharMap).length !== Object.keys(bCharMap).length)でキーの数を比較して、数が異なっていたら早期でfalseを返します。
次にfor文の中でif (aCharMap[char] !== bCharMap[char])を使い、各文字列の同じキーの値(出現回数)がどれか一つでも異なっていたらfalseを返します。

ここまでの処理でfalseを返さなかった場合、最終的にtrueを返すようにします。

index.js

function anagrams(stringA, stringB) {
  // 文字をキー出現回数を値にもつオブジェクト
  const aCharMap = buildCharMap(stringA);
  const bCharMap = buildCharMap(stringB);

  if (Object.keys(aCharMap).length !== Object.keys(bCharMap).length) {
    return false;
  }

  for (let char in aCharMap) {
    if (aCharMap[char] !== bCharMap[char]) {
      return false;
    }
  }

  return true;
}

function buildCharMap(str) {
  let charMap = {};

  // 正規表現を使いすべての半角英数字とアンダースコアに含まれない一文字をすべて''に置き換える
  for (let char of str.replace(/[^\w]/g, '').toLowerCase()) {
    if (charMap[char]) {
      charMap[char]++;
    } else {
      charMap[char] = 1;
    }
  }
  return charMap;
}

母音の総数

引数の文字列に含まれる母音の合計数を返してください。

解答

前の2題と同様に、文字と出現回数のオブジェクトcharMapを作成します。
母音の配列const words = ['a', 'i', 'u', 'e', 'o']を用意し、forの内部で各母音の数をカウントしていきます。

index.js

function vowels(str) {
  let charMap = {};

  for (let char of str.toLowerCase()) {
    if (charMap[char]) {
      charMap[char]++;
    } else {
      charMap[char] = 1;
    }
  }

  const words = ['a', 'i', 'u', 'e', 'o'];
  let count = 0;
  for (word of words) {
    if (charMap[word]) {
      count = count + charMap[word];
    }
  }
  return count;
}

JavaScriptのArrayメソッドを使うともっとシンプルに書くことができます。
例えば、includes()メソッドを使うと以下のようになります。

index.js

function vowels(str) {
  let count = 0;
  const checker = ['a', 'i', 'u', 'e', 'o'];

  for (let char of str.toLowerCase()) {
    if (checker.includes(char)) {
      count++;
    }
  }
  return count;
}

また、match()メソッドを使うことで、正規表現に対する文字列のマッチングの結果matchesを受け取ることができます。
matches.lengthがそのまま結果となります。

index.js

function vowels(str) {
  const matches = str.match(/[aeiou]/gi);
  return matches ? matches.length : 0;
}

【アルゴリズム】JavaScriptで文字列問題を解く

はじめに

頭文字の大文字化

解答

出現最多文字(MaxChars)

解答

アナグラム

解答

母音の総数

解答

参考資料