s1 = gets.chomp.split('')
s2 = gets.chomp.split('')
l1 = s1.length
l2 = s2.length

dp = (l1 + 1).times.map{ [0] * (l2 + 1) }

(0..l1).each{ |y| dp[y][0] = y }
(0..l2).each{ |x| dp[0][x] = x }

for i in (1..l1)
    for j in (1..l2)
        cost = (s1[i-1] == s2[j-1]) ? 0 : 1
        dp[i][j] = [dp[i-1][j] + 1,          #insert
                    dp[i][j-1] + 1,          #delete
                    dp[i-1][j-1] + cost].min #replace
    end
end

puts dp[l1][l2]

