本文涉及知識點

排序 隊列

LeetCode1585. 檢查字符串是否可以通過排序子字符串得到另一個字符串

給你兩個字符串 s 和 t ，請你通過若干次以下操作將字符串 s 轉化成字符串 t ：
選擇 s 中一個 非空 子字符串并將它包含的字符就地 升序 排序。
比方說，對下劃線所示的子字符串進行操作可以由 “14234” 得到 “12344” 。
如果可以將字符串 s 變成 t ，返回 true 。否則，返回 false 。
一個 子字符串 定義為一個字符串中連續的若干字符。
示例 1：
輸入：s = “84532”, t = “34852”
輸出：true
解釋：你可以按以下操作將 s 轉變為 t ：
“84532” （從下標 2 到下標 3）-> “84352”
“84352” （從下標 0 到下標 2） -> “34852”
示例 2：

輸入：s = “34521”, t = “23415”
輸出：true
解釋：你可以按以下操作將 s 轉變為 t ：
“34521” -> “23451”
“23451” -> “23415”
示例 3：

輸入：s = “12345”, t = “12435”
輸出：false
示例 4：

輸入：s = “1”, t = “2”
輸出：false

提示：
s.length == t.length
1 <= s.length <= 10⁵
s 和 t 都只包含數字字符，即 ‘0’ 到 ‘9’ 。

冒泡排序

indexs[i] 是隊列，升序記錄i+'0’的所有下標。
根據冒泡排序的原理，選擇m個字符排序能完成的效果，若干次選擇2個元素排序也能完成。
從小到大枚舉i，如果s[i] < t[i] 返回false
尋找 j > i ，且s[j]等于s[i] ，最小j
如果找不到j，返回false
s[i+1,j-1] 如果有字符小于s[j]，則返回false。
indexs[t[i]-‘0’]] 出隊。
** 注意**：除了頂替當前字符的字符，其它字符的相對位置不變。由于只需要相對順序，所以除替換當前字符的字符出隊外，其它字符都不需要變化。
時間復雜度： O(n)

代碼

核心代碼

class Solution {
public:bool isTransformable(string s, string t) {queue<int> indexs[10];for (int i = 0; i < s.length(); i++) {indexs[s[i] - '0'].emplace(i);}for (int i = 0; i < s.length(); i++) {auto& que = indexs[t[i] - '0'];if (que.empty()) { return false; }for (int j = 0; j < t[i] - '0'; j++) {if (indexs[j].size() && (indexs[j].front() < que.front())) { return false; }}que.pop();}return true;}
};

單元測試

template<class T1,class T2>
void AssertEx(const T1& t1, const T2& t2)
{Assert::AreEqual(t1 , t2);
}template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{Assert::AreEqual(v1.size(), v2.size());	for (int i = 0; i < v1.size(); i++){Assert::AreEqual(v1[i], v2[i]);}
}template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{sort(vv1.begin(), vv1.end());sort(vv2.begin(), vv2.end());Assert::AreEqual(vv1.size(), vv2.size());for (int i = 0; i < vv1.size(); i++){AssertEx(vv1[i], vv2[i]);}
}namespace UnitTest
{string s,  t;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod0){s = "84532", t = "34852";auto res = Solution().isTransformable(s, t);AssertEx(true, res);}TEST_METHOD(TestMethod1){s = "34521", t = "23415";auto res = Solution().isTransformable(s, t);AssertEx(true, res);}TEST_METHOD(TestMethod2){s = "12345", t = "12435";auto res = Solution().isTransformable(s, t);AssertEx(false, res);}TEST_METHOD(TestMethod3){s = "1", t = "2";auto res = Solution().isTransformable(s, t);AssertEx(false, res);}};
}

擴展閱讀

視頻課程

先學簡單的課程，請移步CSDN學院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成戰斗了，為老板分憂，請學習C#入職培訓、C++入職培訓等課程
https://edu.csdn.net/lecturer/6176

相關推薦

我想對大家說的話
《喜缺全書算法冊》以原理、正確性證明、總結為主。
按類別查閱鄙人的算法文章，請點擊《算法與數據匯總》。
有效學習：明確的目標 及時的反饋 拉伸區（難度合適） 專注
聞缺陷則喜(喜缺)是一個美好的愿望，早發現問題，早修改問題，給老板節約錢。
子墨子言之：事無終始，無務多業。也就是我們常說的專業的人做專業的事。
如果程序是一條龍，那算法就是他的是睛

測試環境

操作系統：win7 開發環境： VS2019 C++17
或者 操作系統：win10 開發環境： VS2022 C++17
如無特殊說明，本算法用**C++**實現。