資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學檢查給定的字串是否只能拆分成“ABC”子序列
字串的子序列是指字串的一部分，其中字元可以從字串的任何位置（零個或多個元素）獲取，而不改變字元的順序，從而形成一個新的字串。在這個問題中，我們得到一個長度為N的字串，其中字串的每個字元都屬於'A'、'B'或'C'字元。我們的任務是找到該字串是否只能拆分成“ABC”子序列。如果字串只能拆分成“ABC”子序列，則返回“yes”，否則返回“no”。
Input 1: str = “AABCBC” Output 1: yes
說明 − 拆分的方法是將字串拆分成兩個“ABC”子序列，如下所示：
其中一種可能的方法是，首先透過取索引0、2、3處的字元來形成子序列“ABC”，然後透過取索引1、4、5處的字元來形成子序列“ABC”。
另一種可能的方法是，透過取索引0、4、5和1、2、3處的字元來形成子序列“ABC”。
因此，字串可以拆分成兩個“ABC”子序列。
Input 2: str = “AABBBACCC” Output 2: no
說明 − 對於索引號為5的'A'，其後沒有'B'。因此，整個字串不能只拆分成“ABC”子序列。因此，答案是“no”。
方法1：使用雜湊表
我們有兩個觀察結果：
字串的大小必須能被3整除，因為我們必須將字串拆分成“ABC”，並且'A'、'B'和'C'字元的數量必須相等。否則，我們將無法滿足條件。
當我們計算'A'、'B'和'C'字元的頻率時，'A'的數量必須大於等於'B'的數量，'B'的數量必須大於等於'C'的數量。即 A的數量 >= B的數量 >= C的數量
根據上述觀察結果，我們需要檢查三個條件。
字串大小 % 3 == 0。
A的數量 >= B的數量 >= C的數量。
最後一個條件是 freq['A'] == freq['B'] == freq['C']。
我們可以使用雜湊表來解決這個問題，因為我們需要儲存給定字串“str”中每個字元的頻率。
讓我們逐步討論這種方法：
首先，我們將建立一個函式'checkSubsequences'，該函式將給定的字串'str'作為引數，如果可能則返回所需的字串“yes”，否則返回“no”。
在函式中，以下列出了所有步驟：
建立一個變數'len'來儲存字串的長度。
檢查第一個條件，如果len不能被3整除，則返回'no'。
建立一個雜湊表來儲存'A'、'B'和'C'字元的頻率。因此，空間複雜度是常數。
使用for迴圈遍歷字串，從0到小於len。
增加字串當前字元的計數。
檢查第二個條件，如果'A'的計數小於'B'的計數，或者'B'的計數小於'C'的計數，則返回“no”。
for迴圈結束後，我們必須檢查最終的第三個條件，如果A的計數不等於B的計數，或者B的計數不等於C的計數，則返回“no”。
最後，如果所有條件都滿足，則返回“yes”。
示例
#include <bits/stdc++.h>
using namespace std;
// function to check subsequences of "ABC"
string checkSubsequences( string str ){
int len = str.size(); //getting length of the string str
// check first condition
if( len%3 != 0 ) {
return "no";
}
map< char, int >freq; //store the count of character 'A', 'B' and 'C'
for( int i=0; i<len; i++){
freq[ str[i] ]++; // increase the count of the character
//chech second condition
if(freq[ 'A' ] < freq[ 'B' ] || freq[ 'B' ] < freq[ 'C' ]){
return "no";
}
}
//check third condition
if(freq[ 'A' ] != freq[ 'B' ] || freq[ 'B' ] != freq[ 'C' ]){
return "no";
}
// it is possible to split string only into subsequences of "ABC"
return "yes";
}
// main function
int main(){
string str = "ABAAABCBC";// given string
// calling the function 'checkSubsequences' to check is it possible to split
// string into subsequences of "ABC"
string result = checkSubsequences( str );
if( result == "yes" ){
cout<< result << ", the string is splited only into the subsequences of ABC";
}
else {
cout<< result << ", the string is not splited only into the subsequences of ABC.";
}
return 0;
}
輸出
no, the string is not splited only into the subsequences of ABC.
時間和空間複雜度
上述程式碼的時間複雜度為O(N)，因為我們遍歷了字串。其中N是字串的大小。
上述程式碼的空間複雜度為O(1)，因為我們儲存的是數字的頻率，這是一個常數大小（三個）。
結論
在本教程中，我們實現了一個程式來檢查給定的字串是否只能拆分成“ABC”子序列。我們實現了一種雜湊方法，因為我們必須儲存頻率。在這種方法中，我們必須檢查主要三個條件，如果所有條件都滿足，則意味著我們能夠將字串只拆分成“ABC”子序列。
瀏覽量：164
