関小君刷题记

题目大意：

检查一个字符串是否可以打破另一个字符串

给你两个字符串 s1 和 s2 ，它们长度相等，请你检查是否存在一个 s1  的排列可以打破 s2 的一个排列，或者是否存在一个 s2 的排列可以打破 s1 的一个排列。

字符串 x 可以打破字符串 y （两者长度都为 n ）需满足对于所有 i（在 0 到 n – 1 之间）都有 x[i] >= y[i]（字典序意义下的顺序）。

示例 1：

输入：s1 = "abc", s2 = "xya"
输出：true
解释："ayx" 是 s2="xya" 的一个排列，"abc" 是字符串 s1="abc" 的一个排列，且 "ayx" 可以打破 "abc" 。

示例 2：

输入：s1 = "abe", s2 = "acd"
输出：false
解释：s1="abe" 的所有排列包括："abe"，"aeb"，"bae"，"bea"，"eab" 和 "eba" ，s2="acd" 的所有排列包括："acd"，"adc"，"cad"，"cda"，"dac" 和 "dca"。然而没有任何 s1 的排列可以打破 s2 的排列。也没有 s2 的排列能打破 s1 的排列。

示例 3：

输入：s1 = "leetcodee", s2 = "interview"
输出：true

提示：

• s1.length == n
• s2.length == n
• 1 <= n <= 10^5
• 所有字符串都只包含小写英文字母。

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1433

解题思路分析：

这道题好像是两组人一一PK，看是否能有一组保持不败（非胜即平）。因此，如果想保持不败，必须要保证队伍内无短板。简单来说，如果将两个字符串中的字符都进行升序排序，并且保证其中一个字符串中的每一个字符都要大于等于另一个字符串相应位置的字符的话，本题结果为true，反之为false。

解题时，我们并不需要真的去给字符串进行排序。实际上我们只要统计出每个字符串中每种字符的个数即可。接下来，我们再对字符串进行比较。比较时，我们查看其中一个字符串从a到z每种字符的个数，如果当前字符的个数count1大于0，这时去查看另一个字符串中小于等于该字符的个数count2，如果count2大于等于count1，说明另一个字符串中有更多较小的字符，也就是说当前字符串s1能够战胜s2。反之说明s2中较小的字符个数少，也就是较大的字符个数多，那么获胜的是s2。重复上述过程，直到循环结束。如果s1一直保持不败或者s2一直保持不败返回true，反之返回false。详细实现步骤参见实现代码。

实现代码：

public boolean checkIfCanBreak(String s1, String s2) {
    char[] arrS1 =s1.toCharArray(); // 将s1转为字符数组
    char[] arrS2 =s2.toCharArray(); // 将s2转为字符数组
    int[] count1 = new int[26]; // 统计s1中每种字符个数
    int[] count2 = new int[26]; // 统计s2中每种字符个数
    for(int i=0;i<s1.length();i++){
        count1[arrS1[i]-'a']++;
        count2[arrS2[i]-'a']++;
    }
    // 查看s1是否可以打破s2或者s2可以打破s1
    return isValid(count1,count2)||isValid(count2,count1);
}

boolean isValid(int[] arr1,int[] arr2){
    int[] count1=Arrays.copyOf(arr1,arr1.length);
    int[] count2=Arrays.copyOf(arr2,arr2.length);
    // 循环arr1中a-z每种字符
    for(int i=0;i<26;i++){
        // 当前字符数量
        int c1=count1[i];
        // 数量为0的话，跳过
        if(c1==0) continue;
        // 查看arr2中是否有c1个字符小于等于当前字符
        while(c1>0){
            boolean hasSmall=false;
            // 从0循环至当前字符
            for(int j=0;j<=i;j++){
                // 如果arr2中存在小于arr1当前字符的字符
                if(count2[j]>0){
                    // arr2中该字符个数减一
                    count2[j]--;
                    // 设置从arr2中找到一个小于arr1当前字符的字符
                    hasSmall=true;
                    break;
                }
            }
            // 如果没有从arr2中找到一个小于arr1当前字符的字符，返回false
            if(!hasSmall) return false;
            // arr1中当前字符个数减一
            count1[i]--;
        }
    }
    return true;
}

本题解法执行时间为6ms。

Runtime: 6 ms, faster than 97.05% of Java online submissions for Check If a String Can Break Another String.

Memory Usage: 40.2 MB, less than 100.00% of Java online submissions for Check If a String Can Break Another String.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1433-check-if-a-string-can-break-another-string-解题思路分析/