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

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

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

https://qiita.com/suzuki0430

https://qiita.com/official-events/5a0502a2d94ed6a00c30

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

```
   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`を文字列にして返す


```js: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`として更新していき、更新結果を最後に返します。

```js: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;
}
```

https://qiita.com/nak435/items/0620284e74138ddb3dd4

#アナグラム
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`を返すようにします。

```js: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の内部で各母音の数をカウントしていきます。

```js: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()`メソッドを使うと以下のようになります。

```js: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`がそのまま結果となります。

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

#参考資料
https://www.udemy.com/share/101WNkCEEZd11VRno=/