力扣72编辑距离python

以下是力扣72编辑距离的Python代码实现：

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n1, n2 = len(word1), len(word2)
        dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]
        for i in range(n1 + 1):
            dp[i][0] = i
        for j in range(n2 + 1):
            dp[0][j] = j
        for i in range(1, n1 + 1):
            for j in range(1, n2 + 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], dp[i][j - 1], dp[i - 1][j - 1]) + 1
        return dp[n1][n2]

相关问题

力扣第六题python

力扣第六题是关于将一个给定的字符串按照指定的行数进行Z字形排列的问题。可以使用python来实现此题。

首先，我们可以创建一个 numRows 长度的列表，用来保存每一行的字符。接下来，遍历给定的字符串 s，将字符放入对应的行中。当遍历到第 numRows - 1 行时，需要反向遍历行数，以实现 Z 字形排列。最后，将每一行的字符连接起来，即可得到最终结果。

以下是实现这个算法的示例代码：

def convert(s, numRows):
    if numRows == 1 or numRows >= len(s):
        return s

    rows = [''] * numRows
    index, step = 0, 1

    for char in s:
        rows[index] += char
        if index == 0:
            step = 1
        elif index == numRows - 1:
            step = -1
        index += step

    return ''.join(rows)

力扣有效的括号python

要判断给定的字符串是否是有效的括号，可以使用栈的数据结构来解决。

以下是在 Python 中使用栈来判断有效括号的示例代码：

def isValid(s):
    stack = []
    mapping = {")": "(", "}": "{", "]": "["}
    
    for char in s:
        # 如果当前字符是右括号
        if char in mapping:
            # 栈为空或栈顶元素与当前右括号不匹配，则返回 False
            if not stack or stack[-1] != mapping[char]:
                return False
            # 栈顶元素与当前右括号匹配，将栈顶元素出栈
            stack.pop()
        else:
            # 当前字符是左括号，将其压入栈中
            stack.append(char)
    
    # 如果最终栈为空，则表示所有括号都正确匹配
    return not stack

# 示例
print(isValid("()"))  # True
print(isValid("()[]{}"))  # True
print(isValid("(]"))  # False
print(isValid("([)]"))  # False
print(isValid("{[]}"))  # True

这段代码中，我们使用了一个栈来存储遍历到的括号字符。如果当前字符是左括号，则将其压入栈中；如果当前字符是右括号，则与栈顶元素比较，如果不匹配则返回 False，否则将栈顶元素出栈。最后，如果栈为空，则表示所有括号都正确匹配，返回 True；否则，返回 False。

注意，这里使用了一个字典 `mapping` 来保存右括号与其对应的左括号，方便判断是否匹配。