C++ 中詞彙順序中的最後一個子字串

假設我們有字串 s，我們需要找到 s 中詞彙順序中的最後一個子字串。

因此，如果輸入類似於 “abbbcabbc”，則輸出將是 “cabbc”

為了解決這個問題，我們將按照以下步驟操作 −

  • i := 0，j := 1，k := 0

  • while j + k < s 的大小，執行 &minsu;

    • 如果 s[i + k] 與 s[j + k] 相同，則 −

      • （將 k 增加 1）

      • 忽略以下部分，跳到下一個迭代

    • 如果 s[i + k] < s[j + k]，則 −

      • i := j

      • （將 j 增加 1）

    • 否則

      • j := j + k + 1

    • k := 0

返回從索引 i 到末尾的子字串

讓我們看看以下實現以獲得更好的理解 −

示例

 線上演示

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string lastSubstring(string s) {
      int i = 0;
      int j = 1;
      int k = 0;
      while(j + k < s.size()){
         if(s[i + k] == s[j + k]) {
            k++;
            continue;
         }
         if(s[i + k] < s[j + k]){
            i = j;
            j++;
         }else{
            j = j + k + 1;
         }
         k = 0;
      }
      return s.substr(i, s.size() - i);
   }
};
main(){
   Solution ob;
   cout << (ob.lastSubstring("abbbcabbc"));
}

輸入

"abbbcabbc"

輸出

cabbc

更新於： 2020 年 6 月 4 日

245 瀏覽量

啟動你的 職業生涯

完成課程，獲得認證

開始
廣告