LeetCode #1544 Make The String Great 讓字串變好

Klook.com
文章觀看次數: 65

英文原文如下

Given a string s of lower and upper case English letters.

A good string is a string which doesn’t have two adjacent characters s[i] and s[i + 1] where:

  • 0 <= i <= s.length – 2
  • s[i] is a lower-case letter and s[i + 1] is the same letter but in upper-case or vice-versa.

To make the string good, you can choose two adjacent characters that make the string bad and remove them. You can keep doing this until the string becomes good.

Return the string after making it good. The answer is guaranteed to be unique under the given constraints.

Notice that an empty string is also good.

中文翻譯

給予一個由大小寫英文字母組成的字串 s。

一個好的字串是一個字串沒有兩個相鄰的字元 s[i] 跟 s[i + 1] 符合以下條件:

  • 0 <= i <= 字串 s 的長度 – 2
  • s[i] 是一個小寫字母且 s[i + 1] 是同一個字母但是大寫的，反之亦然(前面大寫後面小寫)

要讓字串變好，你可以選擇兩個會使字串變壞的臨近字元然後移除它們。你可以重複這個動作直到整個字串變好。

回傳變好之後的字串。答案保證是唯一的而且是符合題目限制底下的。

需注意的是，空字串也是好的字串。

範例及題目限制

解題思路

這一題，因為需不斷修改及判斷的特性，我選擇使用 while 迴圈搭配裡面的 for 迴圈 (每次對字串進行的迴圈)來處理

C# 解決方案

⚠️方案1

public class Solution {
    public string MakeGood(string s) {
        
        while(s.Length>1){
            var len = s.Length-1;
            for(int i=0; i<len;i++){
                if(s[i]!=s[i+1] && (char.ToUpper(s[i]) == s[i+1] || char.ToLower(s[i]) == s[i+1])){
                    s = s.Remove(i,2);
                    break;
                }

                if(i==len-1){
                    return s;
                }
            }
        }
        return s;
    }
}

在每次 while 中判斷是否有兩個相鄰的字元導致這個字串是壞的字串，若是有則移除並重設字串再來一次

在寫完後發現有幾個地方可以修正一下的~

方案2 – 使用StringBuilder

public class Solution {
    public string MakeGood(string s) {
        StringBuilder sb = new StringBuilder(s);

        while(sb.Length>1){
            var len = sb.Length-1;
            for(int i=0; i<len;i++){
                if(char.ToUpper(sb[i]) == char.ToUpper(sb[i+1])){
                    if((char.IsUpper(sb[i])&&char.IsLower(sb[i+1])) || (char.IsLower(sb[i])&&char.IsUpper(sb[i+1]))){
                        sb.Remove(i,2);
                        break;
                    }
                }

                if(i==len-1){
                    return sb.ToString();
                }
            }
        }
        return sb.ToString();
    }
}

修正了兩點

  • 改為用 StringBuilder 取代 string 來進行判斷，因為string在多次操作時的效能較為不好
  • 修正 s[i]!=s[i+1] 的那一句判斷，改為先判斷相鄰兩字母是否相同再來進行後續判斷
Klook.com

Java 解決方案

方案1

class Solution {
    public String makeGood(String s) {
        StringBuilder sb = new StringBuilder(s);

        while (sb.length() > 1) {
            int len = sb.length() - 1;
            for (int i = 0; i < len; i++) {
                if (Character.toUpperCase(sb.charAt(i)) == Character.toUpperCase(sb.charAt(i + 1))) {
                    if ((Character.isUpperCase(sb.charAt(i)) && Character.isLowerCase(sb.charAt(i + 1))) ||
                            (Character.isLowerCase(sb.charAt(i)) && Character.isUpperCase(sb.charAt(i + 1)))) {
                        sb.delete(i, i + 2);
                        break;
                    }
                }

                if (i == len - 1) {
                    return sb.toString();
                }
            }
        }

        return sb.toString();
    }
}

結論

🧡如果這篇文章有幫上你的一點點忙，那是我的榮幸

🧡收藏文章或幫我點個廣告，那都是對我的支持

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

題目連結 : Make The String Great – LeetCode

隨機的LeetCode文章

相關文章

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *