- アナグラムの見つけ方を学ぶことで、並び替えの要な概念を使って問題を解決する方法が身に付く
- 剰余演算（モジュロ演算）やリスト内包表記のように日々のプログラミングに役に立つことを本章で学ぶ
目次
用語集
- アナグラム
順番は異なるものの同じ文字で構成されている、2つの文字列 - 回文
前から読んでも後ろから読んでも同じ言葉 - リスト内包表記
既存のイテラブルから新しいリストを作るPythonの構文 - 暗号
暗号化または復号のためのアルゴリズム - 剰余演算
（モジュロ演算）特定の値で折り返すタイプの算術
アナグラムの検出
- 2つの文字列が、順番は異なるものの同じ文字列で構成されているとき、それはアナグラム
- 大文字と小文字は区別しない
- 2つの文字列がアナグラムか否かを確認するには、文字列をソートして比較する
- ソートされた2つの文字列が同じなら、それはアナグラム
- アナグラムを確認する以下のアルゴリズムは、Pythonの組み込み関数
sortedに依存しているので、実行時間はO(n log n)
def is_anagram(s1, s2):
s1 = s1.replace(' ', '').lower()
s2 = s2.replace(' ', '').lower()
if sorted(s1) == sorted(s2):
return True
else:
return False
s1 = 'Emperor Octavian'
s2 = 'Captain over Rome'
print(is_anagram(s1, s2))
>>True回文の検出
- 回文とは、前から読んでも後ろから読んでも同じ文字列のこと
- 文字列が回文かどうかを確認する方法はいくつかある
- 文字列をコピーして、ひっくり返し、元の文字列と比較する方法
- 2つの文字列が等しい場合は、回文
- Pythonでは以下のコードで文字列をひっくり返せる
- 回文を確認するアルゴリズムで、もっとも遅い部分は、小文字に変換する処理と文字列をひっくり返す処理
- これらの処理はすべての要素にアクセスするため、実行時間は
O(n)
'blackswan'[::-1]# 回文チェック
def is_palindrome(s1):
s = s1.lower()
if s == s1[::-1]:
return True
return False最後の数字
- 技術面接でよくある質問は、文字列の1番右側にある数字を返す方法
- たとえば、’Buy 1 get 2 free’ という文字列が与えられた場合、回答は2になる
- この問題を解決する洗練された方法の一つは、Pythonのリスト内包表記を使うこと
- リスト内包表記とは、既存の文字列やリストなどのイテラブルから新しいリストをつくる
new_list = [ 式(x) for x in iterable if 条件(x) ]
- たとえば、以下のリスト内包表記では、変数の
cは文字列selftaughの各文字を一時的に保持する
print([c for c in 'selftaugh'])
>>['s', 'e', 'l', 'f', 't', 'a', 'u', 'g', 'h']- 条件(x)は、新しいつくるリストに追加したい要素を選択する条件となる
- 組み込み関数
ord関数は、文字列のコード値を返す - イテラブルの文字列コード値が102（文字列f）より大きい場合、リストに追加される
[c for c in 'selftaugh' if ord(c) > 102]
>>['s', 'l', 't', 'u', 'g', 'h']# 数字を抽出
s = 'Buy 1 get 2 free'
n1 = [c for c in s if c.isdigit()]
print(n1)
>>['1', '2']- 最初の質問の解答
[n for n in s if n.isdigit()][-1]
>>'2'シーザー暗号（剰余演算）
- 剰余演算は、特定の値で折り返す形の算術
- 時計の読み方を理解していればすでに剰余演算はできている
import string
def cipher(a_string, key):
# 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
uppercase = string.ascii_uppercase
# 'abcdefghijklmnopqrstuvwxyz'
lowercase = string.ascii_lowercase
encrypt = ''
for c in a_string:
if c in uppercase:
# .index(c)で c の位置 ＋ key分ずらし、アルファベット26で割った余り（＝位置）をだす
new = (uppercase.index(c) + key) % 26
encrypt += uppercase[new]
elif c in lowercase:
new = (lowercase.index(c) + key) % 26
encrypt += lowercase[new]
else:
encrypt += c
return encrypt
s = 'abc'
print(cipher(s, 3))