ตรวจสอบว่าสตริงสามารถแบ่งสตริงอื่นใน C ++ . ได้หรือไม่

สมมติว่าเรามีสองสาย s1 และ s2 ที่มีขนาดเท่ากัน เราต้องตรวจสอบว่าการเรียงสับเปลี่ยนของสตริง s1 สามารถทำลายการเรียงสับเปลี่ยนของสตริง s2 หรือในทางกลับกันได้หรือไม่ สตริง a สามารถทำลายสตริง b ถ้า x[i]>=y[i] (ตามลำดับตัวอักษร) สำหรับ i ทั้งหมดในช่วง 0 ถึง n-1

ดังนั้น ถ้าอินพุตเป็นเหมือน s1 =abc และ s2 =xya เอาต์พุตจะเป็นจริง นี่เป็นเพราะว่า "ayx" เป็นการเรียงสับเปลี่ยนของ s2 ที่สามารถแยกสตริง "abc" ซึ่งเป็นการเรียงสับเปลี่ยนของ s1="abc" ได้

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดการตรวจสอบฟังก์ชัน () ซึ่งจะใช้เวลา s1, s2,

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาด s1 อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

  • ถ้า s2[i]

    • คืนค่าเท็จ

• คืนความจริง

• จากวิธีหลัก ให้ทำดังนี้ −

• เรียงลำดับอาร์เรย์ s1

• จัดเรียงอาร์เรย์ s2

• f3 :=ตรวจสอบ (s2, s1)

• f4 :=ตรวจสอบ (s1, s2)

• คืนค่า จริง f3 เป็นจริง หรือ f4 เป็นจริง มิฉะนั้น เท็จ

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool check(string& s1, string& s2){
      for (int i = 0; i < s1.size(); i++) {
         if (s2[i] < s1[i])
            return false;
      }
      return true;
   }
   bool checkIfCanBreak(string s1, string s2) {
      sort(s1.begin(), s1.end());
      sort(s2.begin(), s2.end());
      bool f3 = check(s2, s1);
      bool f4 = check(s1, s2);
      return f3 || f4;
   }
};
main(){
   Solution ob;
   cout << (ob.checkIfCanBreak("abc", "xya"));
}

อินพุต

"abc", "xya"

ผลลัพธ์

1