C++で文字列をパングラム化するコストを計算する方法

はじめに

このチュートリアルでは、C++を使って「文字列をパングラムにするためのコスト」を計算するプログラムについて解説します。

パングラム（パナグラム）とは、アルファベットの26文字すべてを少なくとも1回ずつ含む文や文字列のことです。有名な例として「The quick brown fox jumps over the lazy dog」が挙げられます。

問題の概要

この問題では、次の2つの入力が与えられます。

• 英小文字からなる文字列
• 各アルファベット（a〜z）を1文字追加するのにかかるコストを格納した、長さ26の整数配列

私たちのタスクは、文字列に含まれていないアルファベットを特定し、それらを追加してパングラムを完成させるために必要な合計コストを、与えられた配列をもとに計算することです。

アルゴリズム

1. 長さ26のブール型配列を用意し、すべて false で初期化します。
2. 文字列を先頭から走査し、出現した各文字に対応するインデックスを true に設定します。
3. a〜z の26文字すべてをチェックし、まだ出現していない文字については、対応するコストを合計に加算します。
4. 最終的な合計コストを返します。

実装例（C++）

#include <bits/stdc++.h>
using namespace std;

// パングラムを作成するための
// 合計コストを計算する関数
int calc_cost(int arr[], string str) {
   int cost = 0;
   bool occurred[26] = { false };
   for (int i = 0; i < str.size(); i++)
      occurred[str[i] - 'a'] = true;
   for (int i = 0; i < 26; i++) {
      if (!occurred[i])
         cost += arr[i];
   }
   return cost;
}

int main() {
   int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26 };
   string str = "abcdefghijklmopqrstuvwz";
   cout << calc_cost(arr, str);
   return 0;
}

出力

63

コードの解説

上記の例では、文字列 "abcdefghijklmopqrstuvwz" には n、x、y の3文字が含まれていません。これらの文字のコストは配列の値からそれぞれ 14、24、25 となるため、必要な合計コストは 14 + 24 + 25 = 63 になります。

このアルゴリズムの時間計算量は O(N)（Nは文字列の長さ）、空間計算量は O(1) であり、非常に効率的なアプローチです。