2796. 重复字符串 🔒

🟢   🔗 力扣 LeetCode

题目

Write code that enhances all strings such that you can call the string.replicate(x) method on any string and it will return repeated string x times.

Try to implement it without using the built-in method string.repeat.

Example 1:

Input: str = "hello", times = 2

Output: "hellohello"

Explanation: "hello" is repeated 2 times

Example 2:

Input: str = "code", times = 3

Output: "codecodecode"

Explanation: "code" is repeated 3 times

Example 3:

Input: str = "js", times = 1

Output: "js"

Explanation: "js" is repeated 1 time

Constraints:

• 1 <= times <= 10^5
• 1 <= str.length <= 1000

Follow up: Let's assume, for the sake of simplifying analysis, that concatenating strings is a constant time operation O(1). With this assumption in mind, can you write an algorithm with a runtime complexity of O(log n)?

题目大意

编写代码实现字符串方法 string.replicate(x) ，它将返回重复的字符串 x 次。

请尝试在不使用内置方法 string.repeat 的情况下实现它。

示例 1：

输入： str = "hello", times = 2

输出： "hellohello"

解释： "hello" 被重复了 2 次

示例 2：

输入： str = "code", times = 3

输出： codecodecode"

解释： "code" 被重复了 3 次

示例 3：

输入： str = "js", times = 1

输出： "js"

解释： "js" 被重复了 1 次

提示：

• 1 <= times <= 10^5
• 1 <= str.length <= 1000

进阶 ：为了简化分析，让我们假设连接字符串是一个常数时间操作 O(1)。考虑到这个假设，您能编写时间复杂度为 O(log n) 的算法吗？

解题思路

1. 创建 result 变量用于存放最终结果，curStr 变量为字符串的副本，用于倍增操作。
2. 通过检查 times 是否为奇数，决定是否将 curStr 添加到 result。如果 times 是奇数，需要添加一个 curStr。
3. 每次循环都将 curStr 自我翻倍，并将 times 除以 2，直到 times == 0，这样每次倍增 curStr 时都将工作量减半。

复杂度分析

• 时间复杂度：O(log n)，其中 n = times，因为每次循环 times 都会减半。
• 空间复杂度：O(str.length * times)，用于存储最终的重复字符串，即最终返回的字符串长度。

代码

/**
 * @param {string} str
 * @param {number} times
 * @return {string}
 */
String.prototype.replicate = function (times) {
	let result = '',
		curStr = this;
	while (times > 0) {
		// 如果 times 是奇数，添加当前字符串到结果
		if (times % 2 == 1) {
			result += curStr;
		}

		// 将当前字符串翻倍
		curStr += curStr;

		// 对 times 进行整除 2 操作
		times = (times / 2) | 0;
	}
	return result;
};