iT邦幫忙

1

【小馬的LeetCode練功坊】316, 1081, 1163題- 在字串中找最小、最大的subsequence,找最大的substring

今天練習的是leetcode幾個相似的字串問題,
一起整理分析解答

一、在字串中找出subsequence中包含相異字母字典排序最小的

參考題目:
316. Remove Duplicate Letters
1081. Smallest Subsequence of Distinct Characters

這兩題敘述不同但本質是相同的。
給定一個字串,
316題說,去除重複的字,使剩下的答案為字典排序最小
1081題說找出subsequence中包含相異字母字典排序最小的,
(假設input全由小寫字母組成)
所以input是"ecbacba" 時,
答案都應該是eacb

思路: greedy, 把字串掃過一遍,
如果字元還沒添加到答案字串,儘量添加新的字元到答案裡。
由於每個字元至少會出現一次,
如果添加的字比較小舊的字元在後面也有出現
把舊的字元丟掉沒有關係。

python解

class Solution:
    def smallestSubsequence(self, text: str) -> str:
        ans = []
        for i,c in enumerate(text):
            if c not in ans:
                while ans and c < ans[-1] and ans[-1] in text[i+1:]:
                    ans.pop()
                ans.append(c)
        return ''.join(ans)

c++解

class Solution {
public:
    string smallestSubsequence(string s) {
        unordered_map<char, int> count; //記錄每個字元出現幾次,幫助判斷舊的字元是否在後面有出現
        string res;
        for (auto c : s){
            count[c]++;
        }
        for (auto c : s) {
            count[c]--;
            if (res.find(c)==string::npos){
                while (!res.empty() && c < res.back() && count[res.back()]>0){
                    res.pop_back();
                }
                res.push_back(c);
            }
        }
        return res;
    }
};

二、回傳字串s中,字典序最大的子字串

參考題目: 1163. Last Substring in Lexicographical Order

思路: 一開始看到以為很難,
其實答案一定是一個suffix,就在suffix中找最大值即可。
python的解單純拿suffix來比大小可以過關(但耗時)

python解,AC(760ms)

class Solution:
    def lastSubstring(self, s: str) -> str:
        return max(s[idx:] for idx in range(len(s)))

如果是c++的話就很有意思了,
若硬是直接拿字串的suffix來比大小的話會超時:

c++解,TLE

class Solution {
public:
    string lastSubstring(string s) {
        string res(s);
        for(int i=1; i<s.size();i++){
            string t(s.begin()+i, s.end());
            if(t>res){
                res = t;
            }
        }
        return res;
    }
};

後來參考別人解說才解開,
真的蠻不好想的。

c++解,AC(108ms)

class Solution {
public:
    string lastSubstring(string s) {
        int n=s.size(),i=0,j=1,k=0;
        while(j+k<n)
        {
            if(s[i+k]<s[j+k]){
                i = j++;
                k = 0;
            } 
            else if(s[i+k]>s[j+k]){
                j += k+1;
                k = 0;
            }
            else{
                k++;
            }
        }
        return string(s.begin()+i, s.end());
    }
};

自我練習- 找字串中字典序最大的subsequence

注意這類問題找子字串或subsequence的「最小字典序」並無太大的意義,
因為只要回傳最小的單一字元即為答案。
(就好像說找兩個正整數的「最小公因數」,答案一定是1,太過簡單)

思路: 我覺得想法是如果新添加的字元比舊的字元還要大,
那就一直拿掉舊的字,換上新的更大的字元
(沒有找到對應的題目做,希望思路是對的)

def lastSubseq(s: str) -> str:
    ans = []
    for i,c in enumerate(s):
        while ans and c > ans[-1]:
            ans.pop()
        ans.append(c)
    return ''.join(ans)

尚未有邦友留言

立即登入留言