[Leetcode] 2734. Lexicographically Smallest String After Substring Operation (Medium)

概述

題目

https://leetcode.com/problems/lexicographically-smallest-string-after-substring-operation/
給一字串，求翻轉一段內容，可達到之最小字典排序

心得

週賽吃了 3 個 bug，頭痛的一題…

Array

思路

變換的關鍵在於 a，因為若是遇到則基本不變換，除非全是 a 才需要

程式

class Solution(object):
    def smallestString(self, s):
        """
        :type s: str
        :rtype: str
        """
        
        def cal(s):
            arr = [-1]
            n = len(s)
            for i in range(n):
                if s[i] == "a":
                    arr.append(i)
            if len(arr) == 1:
                return "".join([chr(ord(c)-1) for c in s])
            if arr[1] != 0:
                return "".join([chr(ord(s[i])-1) for i in range(arr[1])]) + s[arr[1]:]
        
        cnt = 0
        n = len(s)
        for i in range(n):
            if s[i] == "a":
                cnt += 1
            else:
                break
        if cnt != n:
            return "a"*cnt + cal(s[cnt:])
        return  "a" * (n-1) + "z"

from lee215 大神，想法相同但 code 精斂得多 Orz

class Solution(object):
    def smallestString(self, s):
        """
        :type s: str
        :rtype: str
        """
        i = 0
        n = len(s)
        s = list(s)
        while i < n and s[i] == 'a':
            i += 1
        if i == n:
            s[-1] = 'z'
        while i < n and s[i] != 'a':
            s[i] = chr(ord(s[i]) - 1)
            i += 1
        return ''.join(s)