Given two strings: s1
and s2
with the same size, check if some permutation of string s1
can break some permutation of string s2
or vice-versa (in other words s2
can break s1
).
A string x
can break string y
(both of size n
) if x[i] >= y[i]
(in alphabetical order) for all i
between 0
and n-1
.
Example 1:
Input: s1 = "abc", s2 = "xya" Output: true Explanation: "ayx" is a permutation of s2="xya" which can break to string "abc" which is a permutation of s1="abc".
Example 2:
Input: s1 = "abe", s2 = "acd" Output: false Explanation: All permutations for s1="abe" are: "abe", "aeb", "bae", "bea", "eab" and "eba" and all permutation for s2="acd" are: "acd", "adc", "cad", "cda", "dac" and "dca". However, there is not any permutation from s1 which can break some permutation from s2 and vice-versa.
Example 3:
Input: s1 = "leetcodee", s2 = "interview" Output: true
Constraints:
s1.length == n
s2.length == n
1 <= n <= 10^5
- All strings consist of lowercase English letters.
Solution 1: Sort and compare
Time complexity: O(nlogn)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua class Solution { public: bool checkIfCanBreak(string s1, string s2) { sort(begin(s1), end(s1)); sort(begin(s2), end(s2)); int f1 = 1; int f2 = 1; for (int i = 0; i < s1.size(); ++i) { f1 &= s1[i] <= s2[i]; f2 &= s1[i] >= s2[i]; } return f1 || f2; } }; |
Solution 2: Counting Sort
The cumulative number of elements must be monotonic e.g. t1 >= t2 or t2 >= t1 for all the letters.
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// Author: Huahua class Solution { public: bool checkIfCanBreak(string s1, string s2) { vector<int> c1(26); vector<int> c2(26); for (int i = 0; i < s1.length(); ++i) { ++c1[s1[i] - 'a']; ++c2[s2[i] - 'a']; } int t1 = 0; int t2 = 0; int f1 = 1; int f2 = 1; for (int i = 0; i < 26; ++i) { t1 += c1[i]; t2 += c2[i]; f1 &= t1 <= t2; f2 &= t2 <= t1; } return f1 || f2; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment