ตรวจสอบว่าสตริงหนึ่งสามารถ Break อีกสตริงหนึ่งได้ใน C++

สมมติว่าเรามีสตริง s1 และ s2 ความยาวเท่ากัน ตรวจสอบว่า permutation ใดของ s1 สามารถ break permutation ใดของ s2 ได้ (หรือกลับกัน) โดย string a break b ได้ถ้า a[i] ≥ b[i] สำหรับทุก i

ตัวอย่าง: s1 = "abc", s2 = "xya" ผลลัพธ์ = true เพราะ "ayx" (perm ของ s2) break "abc" (perm ของ s1)

วิธีแก้ปัญหา

เรียง s1 และ s2 ทั้งคู่
ตรวจสอบ 2 ทิศทาง:
- check(s1, s2): s1[i] ≥ s2[i] ∀i
- check(s2, s1): s2[i] ≥ s1[i] ∀i
ถ้าทิศทางไหนผ่าน คืน true

ตัวอย่างโค้ด C++

#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; 
    } 
}; 

int main(){ 
    Solution ob; 
    cout << (ob.checkIfCanBreak("abc", "xya")); 
}

ข้อมูลนำเข้า

"abc", "xya"