C++で解く「キーボード行」問題：同じ行の文字だけで入力できる単語の見つけ方

英単語のリストが与えられたとき、標準的なQWERTYキーボードレイアウトの同じ行に含まれる文字だけを使って入力できる単語をすべて見つけることを考えます。

例として、入力が ["hello", "world", "mom", "dad", "try", "type", "tom"] であれば、出力は ["dad", "try", "type"] となります。"dad" は中段の文字だけで、「try」と「type」は上段の文字だけで構成されているためです。

キーボードの行と文字の対応

標準的なQWERTY配列は、次の3つの行に分けられます。

• 1行目（上段）：q, w, e, r, t, y, u, i, o, p

• 2行目（中段）：a, s, d, f, g, h, j, k, l

• 3行目（下段）：z, x, c, v, b, n, m

解法の手順

この問題を解くために、以下のステップに従います。

• 結果を格納するための配列 output を定義します。

• フラグ oneRow を true で初期化します。

• マップ charToRowMap を定義し、{文字, 行番号} のペアをすべて登録します。キーはキーボード上に存在する英字、値はその文字が属する行番号です。

• words 配列内の各単語に対して、以下の処理を繰り返します。

  • 単語が空でない場合は、まず oneRow を true にリセットします。

  • 先頭文字を小文字に変換し、charToRowMap から対応する行番号 row を取得します。

  • i = 1 から始めて、i が単語の長さ未満である間、i を1ずつ増やしながら次を繰り返します。

    • charToRowMap[tolower(word[i])] が row と等しくない場合は、oneRow を false に設定し、ループを抜けます。

  • ループ後も oneRow が true（非ゼロ）であれば、その単語を output の末尾に追加します。

• 最後に output を返します。

実装例

それでは、理解を深めるために以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
       cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
public:
    vector<string> findWords(vector<string>& words) {
       vector<string> output;
       bool oneRow = true;
       unordered_map<char, int> charToRowMap{
          { 'q', 1 }, { 'w', 1 }, { 'e', 1 }, { 'r', 1 }, { 't', 1 }, { 'y', 1 }, { 'u', 1 },
{ 'i', 1 }, { 'o', 1 }, { 'p', 1 }, { 'a', 2 }, { 's', 2 }, { 'd', 2 }, { 'f', 2 }, { 'g', 2 }, { 'h', 2 }, { 'j', 2 }, { 'k', 2 }, { 'l', 2 }, { 'z', 3 }, { 'x', 3 }, { 'c', 3 }, { 'v', 3 }, { 'b', 3 }, { 'n', 3 }, { 'm', 3 }
       };
       for (auto word : words)
       if (!word.empty()) {
          oneRow = true;
          int row = charToRowMap[tolower(word[0])];
          for (int i = 1; i < word.length(); i++)
          if (charToRowMap[tolower(word[i])] != row) {
             oneRow = false;
             break;
          }
          if (oneRow)
          output.push_back(word);
       }
       return output;
    }
};
main(){
    Solution ob;
    vector<string> v = {"hello","world","mom","dad","try","type","tom"};
    print_vector(ob.findWords(v));
}

入力

{"hello","world","mom","dad","try","type","tom"}

出力

[dad, try, type]

計算量の評価

時間計算量は O(N × M) です。ここで N は単語の総数、M は単語の平均の長さを表します。各単語について、最大でもその長さ分だけ文字を走査するためです。一方、空間計算量は O(1)（26文字分のマップを保持するため厳密には O(26)）となり、使用する追加データは定数個にとどまります。