文字列判定（動的計画法⑥）

問題

英小文字の文字列 Ｓ があります。

空文字 Ｔ に対して次の操作を繰り返すことで、Ｓ＝Ｔ である状態にできるかどうかを判定してください。

「Ｔ の末尾に"dream"、"dreamer"、"erase"、"eraser"のいずれかを追加する」

解法・ソースコード

まず 再帰関数 を用いた 全探索解法 を考えます。

次のように 再帰関数 を定義します。

rec(i) ← 文字列Ｓの最初のｉ文字分が、"dream"、"dreamer"、"erase"、"eraser"の連結で作れるかどうかを表すブール値（True／False）

文字列Ｓの長さをＮとしたとき、rec(n)が最終的な答えとなります。

rec(i)を求めるために、次の４パターンに分けて考えます。

  • s[0:i]の末尾を”erase”で区切る場合
    rec(i - 5)がTrue かつ s[0:1]の最後の５文字が”erase”であるならば、rec(i)はTrue
  • s[0:i]の末尾を”eraser”で区切る場合
    rec(i - 6)がTrue かつ s[0:1]の最後の５文字が”eraser”であるならば、rec(i)はTrue
  • s[0:i]の末尾を”dream”で区切る場合
    rec(i - 5)がTrue かつ s[0:1]の最後の５文字が”dream”であるならば、rec(i)はTrue
  • s[0:i]の末尾を”dreamer”で区切る場合
    rec(i - 7)がTrue かつ s[0:1]の最後の５文字が”dreamer”であるならば、rec(i)はTrue

この 再帰関数 rec(i) を踏まえて、動的計画法 を表す 配列memo を次のように定義します。

memo[i] ← s[0:i]が、"dream"、"dreamer"、"erase"、"eraser"の連結で作れるどうかを表すブール値（True／False）

memo[0]、memo[1]、…、memo[n] の値を順番に求めていきます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#---------- 入力例 ----------
s = 'erasedream'
#----------------------------
n = len(s)      # 文字列の長さ
memo = [False] * (n + 1)    # メモ化テーブル（動的計画法用の配列）
memo[0] = True

# memo[0]、memo[1]、…、memo[n]を順に求める
for i in range(n + 1):
    if i >= 5 and memo[i - 5] and s[i - 5:i] == 'erase':
        print(i, 'erase')
        memo[i] = True
    if i >= 6 and memo[i - 6] and s[i - 6:i] == 'eraser':
        print(i, 'eraser')
        memo[i] = True
    if i >= 5 and memo[i - 5] and s[i - 5:i] == 'dream':
        print(i, 'dream')
        memo[i] = True
    if i >= 7 and memo[i - 7] and s[i - 7:i] == 'dreamer':
        print(i, 'dreamer')
        memo[i] = True
print('memo', memo)
print('解：Yes' if memo[n] else '解：No')

[実行結果]

5 erase

10 dream

memo [True, False, False, False, False, True, False, False, False, False, True]

解：Yes

“erase” + “dream” で、“erasedream” という文字列が作成できるので、正解は “Yes”（作成できる） となります。