JavaScript 字符串的左旋和右旋
字符串的左旋意味着从前缀一侧按给定字符数逆时针移动并将其添加到后缀一侧。同样,字符串的右旋意味着按给定字符串的字符顺序顺时针移动,但与左旋相反,从后缀选取给定字符数并添加到字符串的前缀。在本文中,我们将实现JavaScript程序来进行给定字符串的左旋和右旋。
问题介绍
在此问题中,我们给定一个字符串和一个数字。该数字表示我们必须将字符串旋转多少次。由于我们对顺时针和逆时针旋转的概念有一些理解,即从给定字符串的开头或前缀一侧或从结尾或后缀一侧获取一些字符,并从它们中删除,然后将其添加到字符串的末尾。
字符串的长度和给定字符串中字符的频率不会改变,只会改变当前字符串的排列。
例如,我们给定一个字符串:apple
那么给定字符串的左旋将为-
- pplea
-
pleap
-
leapp
-
eappl
-
apple
我们可以看到给定字符串的第5次旋转与当前字符串相同,因此不能再进行更多的旋转。
给定字符串的右旋将为-
- eappl
-
leapp
-
pleap
-
pplea
-
apple
我们可以看到给定字符串的第5次右旋与初始字符串相同,因此如果我们继续旋转字符串,不会产生更多的不同结果。
从上面的示例中,我们可以得出结论,通过将字符串向左或向右旋转其长度大小的次数,最终会得到与初始字符串相同的字符串。因此,如果给定的旋转次数大于字符串的长度,则可以使用取模运算,它将给出完全相同的答案。
方法
我们已经了解了字符串左旋和右旋的基本示例,现在让我们逐步介绍一下我们将在之后实现的代码的步骤方法,以便更好地理解。
- 首先,我们将得到的字符串存储在一个变量中,并将所需的旋转次数存储在另一个变量中。我们也可以打印它们以获得更好的比较。
-
我们将创建两个函数,一个用于将字符串向左旋转,另一个用于将字符串向右旋转。
-
对于每个函数,我们将传递给定的字符串和旋转次数变量作为参数。
-
在向左旋转函数中,我们将获取包含最后k个元素的两个子字符串,并将它们的位置交换。
-
在向右旋转函数中,我们将获取包含前k个元素的两个子字符串,并将它们的位置交换。
示例
// function for left rotation
function left_rotation(str,k){
// getting prefix elements and remaining elements
// switiching there place
var new_str = str.substr(k) + str.substring(0,k);
// printing the rotated string
console.log("String after kth left rotation is: " + new_str);
}
// function for right rotation
function right_rotation(str,k){
// getting suffix elements and remaining elements
// switiching there place
var new_str = str.substr(str.length - k) + str.substring(0,str.length-k);
// printing the rotated string
console.log("String after kth rigth rotation is: " + new_str);
}
// given string
var str = "apple"
var k = 2
// printing the given string
console.log("The given string is: " + str);
// getting left rotation
left_rotation(str,k);
// getting right rotation
right_rotation(str,k)
注意
在上述程序中,我们给定了 ‘k’ 或字符串大小以下的旋转次数,如果 k 大于字符串大小,则上述代码会出现错误,但我们已经在介绍部分中看到,在字符串长度之后的旋转次数是重复的,并且可以通过将当前数字与给定字符串长度取模来计算,为了保险起见,我们可以总是这样做 –
k = k % (str.length)
这里,str
是给定的字符串。
时间和空间复杂度
上述代码的时间复杂度为O(N),其中N是给定字符串的大小。在上述代码中,我们只是获取字符串字符并以不同的方式拆分和添加它们,因此时间复杂度是线性的。
上述代码的空间复杂度为O(1),因为我们没有使用任何额外的空间,只是将一个字符串存储到另一个字符串中,所以没有使用额外的空间。
结论
在本教程中,我们实现了JavaScript程序用于给定字符串的左旋转和右旋转。字符串的左旋转意味着给定数量的字符逆时针移动,字符串的右旋转意味着给定数量的字符顺时针移动。我们使用了子字符串的概念,通过它我们将字符串拆分并在另一边添加后缀或前缀。给定程序的时间复杂度为O(N),空间复杂度为O(1)。