プログラミング問題集解答例（問１９）

def question19(s, t):
    dp_table = [[0 for _ in range(len(t) + 1)] for _ in range(len(s) + 1)]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp_table[i + 1][j + 1] = dp_table[i][j] + 1
            else:
                dp_table[i + 1][j + 1] = max(dp_table[i][j + 1], dp_table[i + 1][j])
    return dp_table[len(s)][len(t)]

s = "pencil"
t = "penguin"
question19(s, t)

4

s = "dreamingly"
t = "dreadfully"
question19(s, t)

6

s = "This is a pen. This is an apple."
t = "pen-pineapple-apple-pen"
question19(s, t)

10

s = "There is more to life than increasing its speed. "\
      "(by Mahatma Gandhi)"

t = "There is always light behind the clouds. "\
      "(by Louisa May Alcott)"

question19(s, t)

31

s = "If you want to be successful, it's just this simple: "\
      "Know what you are doing, love what you are doing, "\
      "and believe in what you are doing. "\
      "(by Will Rogers)"

t = "Success is not the key to happiness. "\
      "Happiness is the key to success. "\
      "If you love what you are doing, "\
      "you will be successful. "\
      "(by Louisa May Alcott)"

question19(s, t)

71