5-line Python DP solution

  • 0
    dp = [[0 for j in range(len(s1)+1)] for i in range(len(s2)+1)]
    for i, c2 in enumerate(s2):
        for j, c1 in enumerate(s1):
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + ord(c1) if c1 == c2 else dp[i][j-1])
    return sum(map(ord, list(s1 + s2))) - 2 * dp[len(s2)-1][len(s1)-1]

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.