#3579

Minimum Steps to Convert String with Operations

master · 1635 · lc hard +32 · 42.9% accepted · 45 likes · top 24%

⚑ String Matching DP (LCS / Edit Distance)

Description

Two equal-length strings word1 and word2 are given. Transform word1 into word2 by splitting word1 into contiguous substrings and applying operations on each piece:

- Replace: change one character in the piece to any lowercase letter.

- Swap: exchange any two characters within the piece.

- Reverse: reverse the entire piece.

Each type of operation may involve each position at most once per piece (no index takes part in more than one replace, one swap, or one reverse).

Return the minimum total number of operations needed.

Code

1

2

3

class Solution:
    def minOperations(self, word1: str, word2: str) -> int:

class Solution:
    def minOperations(self, word1: str, word2: str) -> int: