与えられた文字列がヘテログラムかどうかを判定するPythonプログラム

本記事では、与えられた文字列がヘテログラム（Heterogram）であるかどうかを判定するPythonプログラムを解説します。

ヘテログラムとは、同じアルファベットが2回以上出現しない単語・フレーズ・文のことを指します。アルファベット26文字をすべて使用する「パングラム」とは対照的な概念で、両者は以下のように区別されます。

• ヘテログラム：どの文字も繰り返して現れない
• パングラム：アルファベットのすべての文字を使用する

具体例

文字列が abc def ghi の場合：

これはヘテログラムです（繰り返されるアルファベットがない）

文字列が abc bcd dfh の場合：

これはヘテログラムではありません（b、c、d が繰り返されている）

アルゴリズム

ステップ1：文中に含まれるすべてのアルファベットを抽出してリスト化する。
ステップ2：リストをセット（集合）に変換する。セットには重複した値が存在しないため。
ステップ3：セットの長さがアルファベットの総数と一致すれば、各文字が1回ずつしか出現していないことになるため、その文はヘテログラムである。そうでなければヘテログラムではない。

サンプルコード

まずは、サイズ26のハッシュ配列を使って各文字の出現を記録する方法を見ていきましょう。

def stringheterogram(s, n):
    # 各アルファベットの出現を記録する配列
    hash = [0] * 26
    for i in range(n):
        if s[i] != ' ':
            # すでに出現済みの文字であれば False を返す
            if hash[ord(s[i]) - ord('a')] == 0:
                hash[ord(s[i]) - ord('a')] = 1
            else:
                return False
    return True

# 実行部分
s = input("Enter the String ::>")
n = len(s)
print(s, "This string is Heterogram" if stringheterogram(s, n) else "This string is not Heterogram")

セットを使ったより簡潔な実装

Pythonの set() を活用すれば、コードをさらに短く書くこともできます。

def is_heterogram(s):
    # 小文字に変換し、アルファベットのみを抽出してリスト化
    letters = [ch for ch in s.lower() if ch.isalpha()]
    # リストの長さとセットの長さが一致すればヘテログラム
    return len(set(letters)) == len(letters)

s = input("Enter the String ::>")
print(s, "is Heterogram" if is_heterogram(s) else "is not Heterogram")

実行結果

Enter the String ::> asd fgh jkl
asd fgh jkl this string is Heterogram

Enter the String ::>asdf asryy
asdf asryy This string is not Heterogram

まとめ

ヘテログラムの判定は、「各文字が一度だけ出現していること」を確認する問題です。ハッシュ配列を使う方法でも、Pythonのセットを使う方法でも、文字列の長さに対して線形時間 O(n) で効率よく処理できます。実装の際は、空白の扱いや大文字・小文字の正規化に注意しましょう。