Skip to content

Latest commit

 

History

History
212 lines (160 loc) · 6.07 KB

README.md

File metadata and controls

212 lines (160 loc) · 6.07 KB
comments difficulty edit_url rating source tags
true
中等
1513
第 425 场周赛 Q2
哈希表
字符串
排序

3365. 重排子字符串以形成目标字符串

English Version

题目描述

给你两个字符串 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 * 105
  • 1 <= k <= s.length
  • s.length 能被 k 整除。
  • s 和 t 仅由小写英文字母组成。
  • 输入保证 s 和 t 互为字母异位词。

解法

方法一：哈希表

我们记字符串 $s$ 的长度为 $n$，那么每个子字符串的长度为 $m = n / k$。

用一个哈希表 $\textit{cnt}$ 记录每个长度为 $m$ 的子字符串在字符串 $s$ 中出现的次数与在字符串 $t$ 中出现的次数之差。

遍历字符串 $s$，每次取出长度为 $m$ 的子字符串，更新哈希表 $\textit{cnt}$。

最后判断哈希表 $\textit{cnt}$ 中的所有值是否都为 $0$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为字符串 $s$ 的长度。

Python3

class Solution:
    def isPossibleToRearrange(self, s: str, t: str, k: int) -> bool:
        cnt = Counter()
        n = len(s)
        m = n // k
        for i in range(0, n, m):
            cnt[s[i : i + m]] += 1
            cnt[t[i : i + m]] -= 1
        return all(v == 0 for v in cnt.values())

Java

class Solution {
    public boolean isPossibleToRearrange(String s, String t, int k) {
        Map<String, Integer> cnt = new HashMap<>(k);
        int n = s.length();
        int m = n / k;
        for (int i = 0; i < n; i += m) {
            cnt.merge(s.substring(i, i + m), 1, Integer::sum);
            cnt.merge(t.substring(i, i + m), -1, Integer::sum);
        }
        for (int v : cnt.values()) {
            if (v != 0) {
                return false;
            }
        }
        return true;
    }
}

C++

class Solution {
public:
    bool isPossibleToRearrange(string s, string t, int k) {
        unordered_map<string, int> cnt;
        int n = s.size();
        int m = n / k;
        for (int i = 0; i < n; i += m) {
            cnt[s.substr(i, m)]++;
            cnt[t.substr(i, m)]--;
        }
        for (auto& [_, v] : cnt) {
            if (v) {
                return false;
            }
        }
        return true;
    }
};

Go

func isPossibleToRearrange(s string, t string, k int) bool {
	n := len(s)
	m := n / k
	cnt := map[string]int{}
	for i := 0; i < n; i += m {
		cnt[s[i:i+m]]++
		cnt[t[i:i+m]]--
	}
	for _, v := range cnt {
		if v != 0 {
			return false
		}
	}
	return true
}

TypeScript

function isPossibleToRearrange(s: string, t: string, k: number): boolean {
    const cnt: Record<string, number> = {};
    const n = s.length;
    const m = Math.floor(n / k);
    for (let i = 0; i < n; i += m) {
        const a = s.slice(i, i + m);
        cnt[a] = (cnt[a] || 0) + 1;
        const b = t.slice(i, i + m);
        cnt[b] = (cnt[b] || 0) - 1;
    }
    return Object.values(cnt).every(x => x === 0);
}