C言語で文字列内の各数字の出現頻度を求める方法

問題の概要

ある文字列 s が与えられます。この文字列には英字と数字の両方が含まれており、それぞれの数字(0〜9)が出現する回数を求めて表示することが目的です。この問題は、サイズ10の整数配列を用意し、全要素を0で初期化しておくことで簡単に解決できます。文字列を先頭から順に走査し、数字を見つけるたびに対応するインデックスのカウントを1増やしていき、最後に集計結果を出力します。

例として、入力が s = "we85abc586wow236h69" の場合、出力は次のようになります。

(Number 2, Freq 1)
(Number 3, Freq 1)
(Number 5, Freq 2)
(Number 6, Freq 3)
(Number 8, Freq 2)
(Number 9, Freq 1)

アルゴリズムの手順

• サイズ10の配列 freq を定義し、すべての要素を0で初期化します。
• i を0から文字列 s の長さ未満まで1ずつ増やしながら、次の処理を繰り返します。
  • s[i] が数字である場合:
    • freq[s[i] - '0'] の値を1増やします。
• i を0から10未満まで1ずつ増やしながら、次の処理を繰り返します。
  • freq[i] が0より大きい場合:
    • (数字 i, 頻度 freq[i]) を表示します。

C言語による実装例

それでは、実際のコードを見て理解を深めましょう。

#include <stdio.h>
#include <string.h>
void solve(char *s){
    int freq[10] = {0};
    for(int i = 0; i < strlen(s); i++){
        if(s[i] >= '0' && s[i] <= '9'){
            freq[s[i] - '0']++;
        }
    }
    for(int i = 0; i < 10; i++){
        if(freq[i] > 0)
            printf("(Number %d, Freq %d)\n", i, freq[i]);
    }
}
int main(){
    char *s = "we85abc586wow236h69";
    solve(s);
}

入力

"we85abc586wow236h69"

出力

(Number 2, Freq 1)
(Number 3, Freq 1)
(Number 5, Freq 2)
(Number 6, Freq 3)
(Number 8, Freq 2)
(Number 9, Freq 1)

ポイントと計算量

この手法の核心は「s[i] - '0'」という変換です。C言語では文字コード上で '0'〜'9' が連続して配置されているため、各文字から '0' の文字コードを引くことで、対応する整数値(0〜9)を簡単に取得できます。

文字列の長さを n とすると、走査に O(n)、最終的な集計結果の表示に O(10) = O(1) しかかからないため、全体の時間計算量は O(n) となります。また、補助配列のサイズは固定の10なので、空間計算量も O(1) と非常に効率的です。

さらに、<ctype.h> ヘッダーで提供されている isdigit() 関数を使用すれば、「s[i] >= '0' && s[i] <= '9'」という条件判定をより簡潔で可読性の高い形に書き換えることも可能です。