Java 实现字符串左旋转和右旋转

旋转是指将每个字符向前或向后移动。向前移动意味着右旋转（或逆时针），向后移动意味着左旋转（或顺时针）。

在这个问题中，我们给出了一个长度为n的字符字符串和一个整数d，这里d小于n。我们的任务是打印左旋转字符串或右旋转字符串，旋转的位移为d。

只有当前字符串的排列方式改变，给定字符串的长度和字符的频率不变。

输入1

str = “apple”, d = 2

输出 1

Left Rotation = “pleap”
Right Rotation = “leapp”

方法

我们已经看到了给定字符串和整数的示例，让我们来看看这些方法:

方法1：子字符串方法

这种方法的思想是。使用逆向方法旋转字符串。

对于左旋：首先，将字符串的最后n-d个字符添加到第一个d个字符之后。

对于右旋：需要将字符串和字符串大小减去d传递给forLeftRotation函数，以得到右旋字符串。

示例

import java.util.*;
import java.io.*;
public class Rotation{
    // In-place rotation of string str by d to the left.
    static String forLeftRotation(String str, int d)  {
       String first = str.substring(d);
       String second = str.substring(0, d);
       String res = first + second ;
       return res;
    } 
    // In-place rotation of string 'str' by d to the right.
    static String forRightRotation(String str, int d) {
       int n = str.length();
       int newD = n-d;
       return forLeftRotation(str, newD);
    } 
    public static void main(String args[]) {
       String str = "apple"; //given string
       int d = 2; //given integer         
       String strL = str; // store given string for left rotation
       //Call the function to rotate the string toward the left
       strL = forLeftRotation(strL, d);
       System.out.println("Left Rotation: "+strL);        
       String strR = str; // store given string for right rotation
       //Call the function to rotate the string toward the right
       strR = forRightRotation(strR, d);
       System.out.println("Right Rotation: "+strR);            
   }
}

输出

Left Rotation: pleap
Right Rotation: leapp

方法2：使用扩展字符串

思路是我们可以使用一个长度是普通字符串两倍的扩展字符串来进行字符串的旋转。对于左旋转，使用扩展字符串从索引d到索引len(string) + d进行旋转。对于右旋转，将字符串传递给forLeftRotation函数，将字符串左旋转大小为字符串长度减去d。

示例

import java.io.*;
import java.util.*;  
public class Rotation{  
   // rotation of string str by d to the left
   static String forLeftRotation(String str, int d)  {
      String temp = str + str; // Extended string
      int idx = str.length(); // Constructing a new rotated string's index   
      String leftFirst = temp.substring(d, d + idx);    
      return leftFirst; // return left rotated string
   } 
   // Rotating the string str using extended string by d
   static String forRightRotation(String str, int d) {
      return forLeftRotation(str, str.length() - d);
   }
   public static void main(String args[])  {
      String str = "apple"; 
      int d = 2;         
      String strL = forLeftRotation(str, d);
      System.out.println("Left Rotation: "+strL);       
      String strR = forRightRotation(str, d);
      System.out.println("Right Rotation: "+strR);
   }
}

输出

Left Rotation: pleap
Right Rotation: leapp

方法3：使用双端队列

该方法定义了两个基于双端队列的方法，用于将字符串向左和向右旋转。函数forLeftRotation（）和forRightRotation（）分别将字符串str向左和向右旋转d个位置。旋转后的字符串由这两个函数返回。

示例

import java.io.*;
import java.util.*;  
public class Rotation{
   // create function to rotated string towards left
   static String forLeftRotation(String str, int d)   {
      // Create Deque to store characters of the string
      Deque<Character> dq
      = new ArrayDeque<Character>();
      for (char ch : str.toCharArray()) {
         dq.add(ch);
      }
      // first d character of the string is rotated left using deque
      for (int i = 0; i < d; i++) {
         dq.addLast(dq.removeFirst());
      } 
      // convert deque to string
      StringBuilder leftStr = new StringBuilder();
      for (char ch : dq) {
         leftStr.append(ch);
      }
      return leftStr.toString();
   }
   // create function to rotated string towards right
   static String forRightRotation(String str, int d) {
      // Create Deque to store characters of the string
      Deque<Character> dq
      = new ArrayDeque<Character>();
      for (char ch : str.toCharArray()) {
          dq.add(ch);
      } 
      // first d character of the string is rotated right using deque
      for (int i = 0; i < d; i++) {
         dq.addFirst(dq.removeLast());
      } 
      // convert deque to string
      StringBuilder rightStr = new StringBuilder();
      for (char ch : dq) {
         rightStr.append(ch);
      }
      return rightStr.toString();
   }  
   public static void main(String args[]) {
      String str = "apple"; 
      int d = 2;          
      String strL = forLeftRotation(str, d);
      System.out.println("Left Rotation: "+strL);        
      String strR = forRightRotation(str, d);
      System.out.println("Right Rotation: "+strR);
   }
}

输出

Left Rotation: pleap
Right Rotation: leapp

所有上述3个方法的注意事项

在上述3个方法中，我们给出了’d’或字符串大小以下的旋转次数，如果d大于字符串大小，则以上代码将会报错。但为了保险起见，我们总是可以这样做 –

d = d % (str.length())

结论

本文讨论了字符串的左右旋转的Java程序。为了解决这个问题，实现了三种方法。它们分别是使用子字符串方法、扩展字符串方法和双端队列方法，它们的时间复杂度均为O(N)。