Medium

题目描述

给你两个字符串 s 和 t，它们互为字母异位词，以及一个整数 k。

你的任务是确定是否可以将字符串 s 分割成 k 个等长的子字符串，重新排列这些子字符串，并按任意顺序连接它们，以创建一个与给定字符串 t 匹配的新字符串。

如果可能，返回 true，否则返回 false。

字母异位词是通过重新排列不同单词或短语的字母形成的单词或短语，恰好使用所有原始字母一次。

子字符串是字符串中连续的非空字符序列。

示例 1：

输入：s = "abcd", t = "cdab", k = 2
输出：true
解释：
将 s 分割成 2 个长度为 2 的子字符串：["ab", "cd"]。
将这些子字符串重新排列为 ["cd", "ab"]，然后连接它们得到 "cdab"，与 t 匹配。

示例 2：

输入：s = "aabbcc", t = "bbaacc", k = 3
输出：true
解释：
将 s 分割成 3 个长度为 2 的子字符串：["aa", "bb", "cc"]。
将这些子字符串重新排列为 ["bb", "aa", "cc"]，然后连接它们得到 "bbaacc"，与 t 匹配。

示例 3：

输入：s = "aabbcc", t = "bbaacc", k = 2
输出：false
解释：
将 s 分割成 2 个长度为 3 的子字符串：["aab", "bcc"]。
这些子字符串无法重新排列形成 t = "bbaacc"，所以输出为 false。

约束条件：

  • 1 <= s.length == t.length <= 2 * 10^5
  • 1 <= k <= s.length
  • s.length 可被 k 整除
  • s 和 t 仅包含小写英文字母
  • 输入保证 s 和 t 互为字母异位词

解题思路

这道题的核心思路是判断将字符串 s 按固定长度分割后的子字符串集合，是否与将字符串 t 按同样方式分割后的子字符串集合完全相同。

解题思路：

  1. 分割字符串：首先计算每个子字符串的长度 len = s.length / k，然后将 s 和 t 都按这个长度进行分割。

  2. 频次统计：使用哈希表分别统计从 s 和 t 中得到的子字符串的出现频次。如果两个字符串可以通过重新排列子字符串得到相同结果，那么它们分割后的子字符串集合应该完全相同。

  3. 比较验证：比较两个哈希表是否完全相等。如果相等，说明可以通过重新排列 s 的子字符串来构成 t。

算法优化：

  • 可以只用一个哈希表，对 s 的子字符串进行 +1 操作，对 t 的子字符串进行 -1 操作
  • 最后检查哈希表中所有值是否都为 0

这种方法的时间复杂度主要取决于字符串长度和分割操作，空间复杂度取决于不同子字符串的数量。

代码实现

class Solution {
public:
    bool isPossibleToRearrange(string s, string t, int k) {
        int n = s.length();
        int len = n / k;
        
        unordered_map<string, int> count;
        
        // 统计 s 中子字符串频次（+1）
        for (int i = 0; i < n; i += len) {
            string sub = s.substr(i, len);
            count[sub]++;
        }
        
        // 统计 t 中子字符串频次（-1）
        for (int i = 0; i < n; i += len) {
            string sub = t.substr(i, len);
            count[sub]--;
        }
        
        // 检查所有计数是否为 0
        for (auto& p : count) {
            if (p.second != 0) {
                return false;
            }
        }
        
        return true;
    }
};

class Solution:
    def isPossibleToRearrange(self, s: str, t: str, k: int) -> bool:
        n = len(s)
        length = n // k
        
        count = {}
        
        # 统计 s 中子字符串频次（+1）
        for i in range(0, n, length):
            sub = s[i:i + length]
            count[sub] = count.get(sub, 0) + 1
        
        # 统计 t 中子字符串频次（-1）
        for i in range(0, n, length):
            sub = t[i:i + length]
            count[sub] = count.get(sub, 0) - 1
        
        # 检查所有计数是否为 0
        return all(cnt == 0 for cnt in count.values())

public class Solution {
    public bool IsPossibleToRearrange(string s, string t, int k) {
        int n = s.Length;
        int len = n / k;
        
        Dictionary<string, int> count = new Dictionary<string, int>();
        
        // 统计 s 中子字符串频次（+1）
        for (int i = 0; i < n; i += len) {
            string sub = s.Substring(i, len);
            count[sub] = count.GetValueOrDefault(sub, 0) + 1;
        }
        
        // 统计 t 中子字符串频次（-1）
        for (int i = 0; i < n; i += len) {
            string sub = t.Substring(i, len);
            count[sub] = count.GetValueOrDefault(sub, 0) - 1;
        }
        
        // 检查所有计数是否为 0
        foreach (var kvp in count) {
            if (kvp.Value != 0) {
                return false;
            }
        }
        
        return true;
    }
}

var isPossibleToRearrange = function(s, t, k) {
    const n = s.length;
    const len = n / k;
    
    const count = new Map();
    
    // 统计 s 中子字符串频次（+1）
    for (let i = 0; i < n; i += len) {
        const sub = s.substring(i, i + len);
        count.set(sub, (count.get(sub) || 0) + 1);
    }
    
    // 统计 t 中子字符串频次（-1）
    for (let i = 0; i < n; i += len) {
        const sub = t.substring(i, i + len);
        count.set(sub, (count.get(sub) || 0) - 1);
    }
    
    // 检查所有计数是否为 0
    for (const cnt of count.values()) {
        if (cnt !== 0) {
            return false;
        }
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n)
空间复杂度O(k)

说明：

  • 时间复杂度：O(n)，其中 n 是字符串长度。需要遍历字符串两次进行分割和统计
  • 空间复杂度：O(k)，最多存储 k 个不同的子字符串在哈希表中