Java中排序字符数组后，如何判断其一对应另一的子串？（LeetCode567）

题目回顾 #

给定两个字符串s1和s2，判断s2是否包含s1的任意排列（即s1的某个排列是s2的子串），是则返回true，否则返回false。

示例：

• 输入s1 = "ab"，s2 = "eidbaooo"，输出true（s2包含s1的排列"ba"）
• 输入s1 = "ab"，s2 = "eidboaoo"，输出false

排序后的匹配步骤 #

你已经完成将s1转为字符数组并排序的步骤，接下来可以按以下逻辑实现匹配：

1. 边界判断：如果s2的长度小于s1，直接返回false——更短的字符串不可能包含更长字符串的排列。
2. 生成目标基准：将排序后的s1字符数组转回字符串，记为target（比如s1="ab"排序后得到"ab"）。
3. 滑动窗口遍历：在s2中滑动一个长度等于s1的窗口，对每个窗口内的子串执行以下操作：
   • 将子串转为字符数组并排序
   • 把排序后的子串和target对比，若相等则说明该子串是s1的排列，直接返回true
4. 遍历结束无匹配：如果所有窗口都遍历完仍未找到匹配，返回false

代码示例（Java） #

import java.util.Arrays;

public class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) {
            return false;
        }
        
        char[] s1Chars = s1.toCharArray();
        Arrays.sort(s1Chars);
        String target = new String(s1Chars);
        
        int windowSize = s1.length();
        for (int i = 0; i <= s2.length() - windowSize; i++) {
            String windowSub = s2.substring(i, i + windowSize);
            char[] windowChars = windowSub.toCharArray();
            Arrays.sort(windowChars);
            if (new String(windowChars).equals(target)) {
                return true;
            }
        }
        
        return false;
    }
}

注意事项 #

• 窗口长度必须严格等于s1的长度，因为排列的长度和原字符串完全一致
• 该方法的时间复杂度为O(n*k log k)（n是s2长度，k是s1长度），对于k较小的场景效率足够；如果k很大，字符计数法（统计每个字符出现次数）会更高效，但排序法的实现逻辑更直观。

内容的提问来源于stack exchange，提问作者Keerthi Kodali