Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details

preface

This is the fourth question in the Biweekly Contest 73. It focuses on the concept of palindromes and greedy algorithms.

describe

You are given a string s consisting only of lowercase English letters.In one move, you can select any two adjacent characters of s and swap them.Return the minimum number of moves needed to make s a palindrome.

Note that the input will be generated such that s can always be converted to a palindrome.

Example 1:

Input: s = "aabb"
Output: 2
Explanation:
We can obtain two palindromes from s, "abba" and "baab". 
- We can obtain "abba" from s in 2 moves: "aabb" -> "abab" -> "abba".
- We can obtain "baab" from s in 2 moves: "aabb" -> "abab" -> "baab".
Thus, the minimum number of moves needed to make s a palindrome is 2.
Copy the code

Note:

1 <= s.length <= 2000
s consists only of lowercase English letters.
s can be converted to a palindrome using a finite number of moves.
Copy the code

parsing

Given a string s consisting only of lowercase English letters. Use the move operation to select any two adjacent characters of S and swap them. Returns the minimum number of moves required to make s a palindrome. They already guarantee that the input s will form a palindrome.

I didn’t solve this problem in the contest, but after I read some of the big guys’ solutions, there are two solutions that are easier to understand. First, let’s introduce the first one. Suppose we have an S that is Lceetelet:

  • We take the first letter L as the benchmark and look for L from the last character. After finding it, we use two operation transformations to get LceeteetL by exchanging characters.
  • Len (s)//2-1 = len(s)//2-1 = len(s)//2-1 = len(s)//2-1 Let it go for the moment
  • We take the third letter e as the benchmark, and start looking from the penultimate character forward. After finding it, we use only one operation change, and then swap it to get lceetetel
  • We start with the fourth letter, e, and work our way up from the third to last character. After we find it, we use only one operation change, and then swap to get lceetteel
  • Now that we’re done, all we need to do is put the single C in the middle, and we’ll have Leetcteel. A total of seven operations were consumed.

The time complexity is O(N^2 * CONCAT). CONCAT refers to the concatenation of strings in one step of the code, which is time-consuming. The space complexity is O(N).

answer

class Solution(object):
    def minMovesToMakePalindrome(self, s):
        result = 0
        N = len(s)
        target = N - 1 
        for i in range(N//2):
            for j in range(target, i-1, -1):
                if j == i:
                    result += N // 2 - i
                elif s[i] == s[j]:
                    s = s[:j] + s[j + 1 : target + 1] + s[j] + s[target + 1:]
                    result += target - j
                    target -= 1
                    break
        return result	
Copy the code

The results

129/129 Test cases passed. Status: Accepted Runtime: 1027 MS Memory Usage: 13.6 MBCopy the code

parsing

The other big guy has a much simpler idea, which is to use a greedy algorithm, essentially the same idea as above, which is to constantly determine the first and last characters of the string, and then move down the middle to determine the second and penultimate characters, and so on.

And this guy’s solution is a lot simpler than the one above. Although time and space complexity are the same, there are subtle differences. Because one of the above steps is to concatenate strings, it takes quite a long time, running 1027 ms, while this solution is purely numerical operation, so it takes only 83 ms. In the process of the while loop, as the elements at both ends keep popping up, the length of S becomes shorter and shorter, and the execution time of index becomes shorter and shorter, which is another reason why this solution takes less time. The big man is really good, the solution is very clever.

answer

class Solution(object):
    def minMovesToMakePalindrome(self, s):
        result = 0
        s = list(s)
        res = 0
        while s:
            i = s.index(s[-1])
            if i == len(s) - 1:
                res += i / 2
            else:
                res += i
                s.pop(i)
            s.pop()
        return res
Copy the code

The results

129/129 Test cases passed. Status: Accepted Runtime: 83 MS Memory Usage: 13.6 MBCopy the code

The original link

Leetcode.com/contest/biw…

Your support is my biggest motivation