🐰😺✏️ 兔猫信奥学院的编辑距离探险 ✏️😺🐰

在信奥学院的练习室里，加菲老师给小兔和小猫出了个新挑战：“给定两个单词 word1 和 word2，你们可以对单词做三种操作——插入、删除或替换一个字符，问最少需要多少步才能把 word1 变成 word2？”故事说完，下面正式进入信息学奥赛® 题目。

输入格式

输入两行：  
第一行包含字符串 word1；  
第二行包含字符串 word2。  

• $0 \le |\,\text{word1}\,|,\,|\,\text{word2}\,| \le 500$
• 两个字符串均由小写英文字母组成。

输出格式

输出一个整数，表示将 word1 转换成 word2 所需的最少操作数。  

样例 1

horse
ros

3

• 解释：

  horse → rorse   （将 'h' 替换为 'r'）
  rorse → rose    （删除第一个 'r'）
  rose  → ros     （删除 'e'）
  

  共 3 步。

样例 2

intention
execution

5

• 解释：

  intention → inention   （删除 't'）
  inention → enention   （将 'i' 替换为 'e'）
  enention → exention   （将 'n' 替换为 'x'）
  exention → exection   （将 'n' 替换为 'c'）
  exection → execution  （插入 'u'）
  

  共 5 步。

祝编辑距离探险顺利，算法更进一步！