1. 简化路径
给定一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请将其转化为 更加简洁的规范路径。
在 Unix 风格的文件系统中规则如下：
- 一个点 '.' 表示当前目录本身。
- 此外，两个点 '..' 表示将目录切换到上一级（指向父目录）。
- 任意多个连续的斜杠（即，'//' 或 '///'）都被视为单个斜杠 '/'。
- 任何其他格式的点（例如，'...' 或 '....'）均被视为有效的文件/目录名称。
返回的 简化路径 必须遵循下述格式：
- 始终以斜杠 '/' 开头。
- 两个目录名之间必须只有一个斜杠 '/' 。
- 最后一个目录名（如果存在）不能 以 '/' 结尾。
- 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。
class Solution:
def simplifyPath(self, path: str) -> str:
stack = []
parts = path.split('/')
for part in parts:
if part == '..':
if stack:
stack.pop()
elif part and part!= '.':
stack.append(part)
return '/' + '/'.join(stack)
2. 编辑距离
给定两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1)
return dp[m][n]