logo

TechCodeview

文字列の左回転

文字列を与える s そして整数 d 任務は 左回転  による文字列  d  ポジション。

例:

入力 : s = 'オタクのためのオタク' d = 2
出力 : 'exforGeeksGe'
説明 : 最初の回転文字列 s が ' になった後、 eeksforGeeksG' 2 回目の回転後は ' になります。 exforGeeksGe' 。



入力 : s = 'qwertyu' d = 2
出力 : 'エルトゥク'
説明 : 最初の回転文字列 s が ' になった後 ヴェルク」 2 回目の回転後は ' になります。 エルトゥク 。

目次

[単純なアプローチ] 1 つずつ左回転

T 彼のアイデアは、 初め 変数内の文字と シフト すべての 残り の文字 左 1 つの位置を移動してから、 初め 文字列の末尾の文字。このプロセスが繰り返される d 回。

C++ 
// C++ Program to left rotate the string by d  // positions by rotating one element at a time #include    #include  using namespace std;   void rotateString(string &s int d) {  int n = s.size();  // Repeat the rotation d times  for (int i = 0; i < d; i++) {  // Left rotate the string by one position  int first = s[0];  for (int j = 0; j < n - 1; j++)   s[j] = s[j + 1];    // Place the first character at the end  s[n - 1] = first;  } } int main() {  string s = 'GeeksforGeeks';  int d = 2;  rotateString(s d);  cout << s << endl;  return 0; }
C 
// C Program to left rotate the string by d positions // by rotating one element at a time #include  #include  void rotateString(char s[] int d) {  int n = strlen(s);  // Repeat the rotation d times  for (int i = 0; i < d; i++) {  // Left rotate the string by one position  char first = s[0];  for (int j = 0; j < n - 1; j++)   s[j] = s[j + 1];    // Place the first character at the end  s[n - 1] = first;  } } int main() {  char s[] = 'GeeksforGeeks';  int d = 2;  rotateString(s d);  printf('%sn' s);  return 0; }
Java 
// Java Program to left rotate the string by d positions // by rotating one element at a time import java.util.Arrays; class GfG {  static String rotateString(String s int d) {  // Convert the string to a char array  char[] charArray = s.toCharArray();  int n = charArray.length;  // Perform the rotation d times  for (int i = 0; i < d; i++) {  // Store the first character  char first = charArray[0];  // Shift each character one position to  // the left  for (int j = 0; j < n - 1; j++)  charArray[j] = charArray[j + 1];  // Move the first character to the end  charArray[n - 1] = first;  }    return new String(charArray);  }  public static void main(String[] args) {  String s = 'GeeksforGeeks';  int d = 2;  String rotatedString = rotateString(s d);  System.out.println(rotatedString);  } }
Python 
# python Program to left rotate the string by d  # positions by rotating one element at a time def rotateString(s d): # Convert the string to a list of  # characters s = list(s) n = len(s) # Perform the rotation d times for _ in range(d): # Store the first character first = s[0] # Shift each character one  # position to the left for i in range(n - 1): s[i] = s[i + 1] # Move the first character to the end s[n - 1] = first # Convert the list back to a string return ''.join(s) s = 'GeeksforGeeks' d = 2 rotatedString = rotateString(s d) print(rotatedString)
C# 
// C# Program to left rotate the string by d positions // by rotating one element at a time using System; class GfG {  static string rotateString(string s int d) {    // Convert the string to a character array  char[] charArray = s.ToCharArray();  int n = charArray.Length;  // Perform the rotation d times  for (int i = 0; i < d; i++) {    // Store the first character  char first = charArray[0];  // Shift each character one position to   // the left  for (int j = 0; j < n - 1; j++)   charArray[j] = charArray[j + 1];  // Move the first character to the end  charArray[n - 1] = first;  }  // Convert the character array to a string  return new string(charArray);  }  static void Main() {  string s = 'GeeksforGeeks';  int d = 2;  string rotatedString = rotateString(s d);  Console.WriteLine(rotatedString);  } }
JavaScript 
// Javascript Program to left rotate the string by d positions // by rotating one element at a time function rotateString(s d) {  // Convert the string to an array  let charArray = s.split('');  let n = charArray.length;  // Perform the rotation d times  for (let i = 0; i < d; i++) {    // Store the first character  let first = charArray[0];    // Shift each character one position to the left  for (let j = 0; j < n - 1; j++)   charArray[j] = charArray[j + 1];    // Move the first character to the end  charArray[n - 1] = first;  }  // Convert the array back to a string  return charArray.join(''); } let s = 'GeeksforGeeks'; let d = 2; let rotatedString = rotateString(s d); console.log(rotatedString);

出力 
eksforGeeksGe

時間計算量:  O(n*d) 外側のループが実行される  d   時間と内部ループの実行 n  回。
補助スペース: 文字列が次の場合は O(1) 可変 C++ のように。のために 不変文字列 Java C# Python や Javascript と同様に、サイズ n の追加の文字配列が使用されるため、空間複雑度は O(n) になります。

[より良いアプローチ] 一時的な Char 配列を使用する

このアイデアは、次のサイズの一時的な文字配列を使用することです。 n (元の文字列のサイズ)。文字列を左に回転すると、 d 最後に配置する n – d 要素は次の場所にあります フロント そして最初の d 要素は次の場所にあります 終わり 。

データ構造を試す
  • をコピーします 最後の (n – d) 要素 元の文字列を最初に挿入 n – d 一時配列の位置。
  • 次に、 最初の d 要素 元の文字列から一時配列の最後まで。
  • ついに 変換する 一時的な char 配列を文字列に変換します。
C++ 
// C++ program to left rotate a string by d // position using a temporary array #include    #include  using namespace std; string rotateString(string &s int d) {  int n = s.length();  // Handle cases where d > n  d = d % n;  char temp[n];  // Copy the last (n - d) characters  // to the start of temp Array  for (int i = 0; i < n - d; i++)  temp[i] = s[d + i];  // Copy the first d characters to the end  // of temp Array  for (int i = 0; i < d; i++)  temp[n - d + i] = s[i];  // Convert temp array to the string  return string(temp n); } int main() {  string s = 'GeeksforGeeks';  int d = 2;  string rotatedString = rotateString(s d);  cout << rotatedString << endl;  return 0; }
Java 
// Java program to left rotate a string by d position // using a temporary array import java.io.*; class GfG {  static String rotateString(String s int d) {  int n = s.length();    // Handle cases where d > n  d = d % n;   char[] temp = new char[n];  // Copy the last (n - d) characters to the   // start of temp array  for (int i = 0; i < n - d; i++)   temp[i] = s.charAt(d + i);  // Copy the first d characters to the end of  // temp array  for (int i = 0; i < d; i++)   temp[n - d + i] = s.charAt(i);  // Convert the temp array back to the String   return new String(temp);  }  public static void main(String[] args) {  String s = 'GeeksforGeeks';  int d = 2;  String rotatedString = rotateString(s d);  System.out.println(rotatedString);  } }
Python 
# Python program to left rotate a string  # by d position using a temporary array def rotateString(s d): n = len(s) # Handle cases where d > n d = d % n # Create a temporary array of the # same length as s temp = [''] * n # Copy the last (n - d) characters  # to the start of temp array for i in range(n - d): temp[i] = s[d + i] # Copy the first d characters to the  #end of temp array for i in range(d): temp[n - d + i] = s[i] # Convert temp array back to the string return ''.join(temp) s = 'GeeksforGeeks' d = 2 rotatedString = rotateString(s d) print(rotatedString)
C# 
// C# program to left rotate a string by d position  // using temporary array using System; class GfG {  static string rotateString(string s int d) {  int n = s.Length;  // Handle cases where d > n  d = d % n;  char[] temp = new char[n];  // Copy the last (n - d) characters   // to the start of temp array  for (int i = 0; i < n - d; i++)   temp[i] = s[d + i];    // Copy the first d characters to the end   // of temp array  for (int i = 0; i < d; i++)   temp[n - d + i] = s[i];    // Convert temp array back to the string  return new string(temp);  }  static void Main() {  string s = 'GeeksforGeeks';  int d = 2;  string rotatedString = rotateString(s d);  Console.WriteLine(rotatedString);  } }
JavaScript 
// Javascript program to left rotate a string  // by d position using temporary array function rotateString(s d) {  let n = s.length;  // Handle cases where d > n  d = d % n;  let temp = new Array(n);  // Copy the last (n - d) characters to   // the start of temp array  for (let i = 0; i < n - d; i++)   temp[i] = s[d + i];    // Copy the first d characters   // to the end of temp array  for (let i = 0; i < d; i++)   temp[n - d + i] = s[i];    // Convert the array back to the string  return temp.join(''); } let s = 'GeeksforGeeks'; let d = 2; let rotatedString = rotateString(s d); console.log(rotatedString);

出力 
eksforGeeksGe

時間計算量:  各要素を 2 回だけ訪問しているため、O(n)。
補助スペース:  追加の文字配列を使用しているため、O(n)。

【想定されるアプローチ-1】ジャグリングアルゴリズムの利用

ジャグリング アルゴリズムの背後にある考え方は、すべての要素を周期的に回転させることができるということです。 それぞれのサイクルは、 独立した 回転中に要素間で移動する要素のグループを表します。もし 起動 サイクルのインデックスは 私 そうすれば、サイクルの次の要素がインデックスに存在します。 (i + d) %n (i + 2d) %n (i + 3d) %n ...インデックス i に戻るまで続きます。合計サイクル数は次のようになります。 n と d の GCD 。そして私たちは、 左一回転 各サイクル内で。

ジャグリング アルゴリズムの詳細については、この記事を参照してください。 配列回転のためのジャグリング アルゴリズム 。

C++ 
// C++ Program to left rotate the string by d positions // using Juggling Algorithm #include    #include  #include    using namespace std; void rotateString(string &s int d) {  int n = s.size();  // Handle the case where d > size of array  d %= n;  // Calculate the number of cycles in the rotation  int cycles = __gcd(n d);  // Perform a left rotation within each cycle  for (int i = 0; i < cycles; i++) {  // Start element of current cycle  char startChar = s[i];  // Start index of current cycle  int currIdx = i nextIdx;  // Rotate elements till we reach the start of cycle  while (true) {  nextIdx = (currIdx + d) % n;  if (nextIdx == i)  break;  // Update the next index with the current element  s[currIdx] = s[nextIdx];  currIdx = nextIdx;  }  // Copy the start element of current cycle   // at the last index of the cycle  s[currIdx] = startChar;  } } int main() {  string s = 'GeeksforGeeks';  int d = 2;  rotateString(s d);  cout << s << endl;  return 0; }
C 
// C Program to left rotate the string by d positions // using Juggling Algorithm #include  #include  void rotateString(char s[] int d) {  int n = strlen(s);  // Handle the case where d > size of array  d %= n;  // Calculate the number of cycles in the  // rotation  int cycles = gcd(n d);  // Perform a left rotation within each cycle  for (int i = 0; i < cycles; i++) {  // Start element of the current cycle  char startChar = s[i];  // Start index of the current cycle  int currIdx = i nextIdx;  // Rotate elements until we return to the  // start of the cycle  while (1) {  nextIdx = (currIdx + d) % n;  if (nextIdx == i)  break;  // Update the current index with the  // element at the next index  s[currIdx] = s[nextIdx];  currIdx = nextIdx;  }  // Place the start element of the current  // cycle at the last index  s[currIdx] = startChar;  } } int gcd(int a int b) {  if (b == 0)  return a;  return gcd(b a % b); } int main() {  char s[] = 'GeeksforGeeks';  int d = 2;  rotateString(s d);  printf('%sn' s);  return 0; }
Java 
// Java Program to left rotate the string by d positions // using Juggling Algorithm import java.io.*; class GfG {  static String rotateString(String s int d) {  int n = s.length();  // Handle the case where   // d > size of the string  d %= n;  // Calculate the number of   // cycles (GCD of n and d)  int cycles = gcd(n d);  // Convert string to character array  char[] arr = s.toCharArray();  // Perform a left rotation within each cycle  for (int i = 0; i < cycles; i++) {    // Start element of current cycle  char temp = arr[i];  int j = i;  while (true) {  int k = (j + d) % n;  if (k == i) {  break;  }  // Move the element to the next index  arr[j] = arr[k];  j = k;  }    // Place the saved element in the   // last position of the cycle  arr[j] = temp;  }  // Convert the rotated character   // array back to a string  return new String(arr);  }  // function to calculate GCD of two numbers  static int gcd(int a int b) {  if (b == 0) {  return a;  }  return gcd(b a % b);  }  public static void main(String[] args) {  String s = 'GeeksforGeeks';  int d = 2;  String rotatedString = rotateString(s d);  System.out.println(rotatedString);  } }
Python 
# python Program to left rotate the string by  # d positions using Juggling Algorithm def gcd(a b): while b: a b = b a % b return a def rotateString(s d): n = len(s) # Handle the case where d > size of # the string d %= n # Calculate the number of cycles (GCD # of n and d) cycles = gcd(n d) # Convert string to a list of characters arr = list(s) # Perfrom a left rotation wihtin each cycle for i in range(cycles): # Start element of current cycle temp = arr[i] j = i while True: k = (j + d) % n if k == i: break # Move the element to the next # index arr[j] = arr[k] j = k # Place the saved element in the last # position of the cycle arr[j] = temp # Convert the list of characters back to # a string and return return ''.join(arr) s = 'GeeksforGeeks' d = 2 rotatedString = rotateString(s d) print(rotatedString)
C# 
// C# Program to left rotate the string by d positions // using Juggling Algorithm using System; class GfG {  static int Gcd(int a int b) {  while (b != 0) {  int temp = b;  b = a % b;  a = temp;  }  return a;  }  static string rotateString(string s int d) {  int n = s.Length;  // Handle the case where d > size of the string  d %= n;  // Calculate the number of cycles (GCD of n and d)  int cycles = Gcd(n d);  // Convert string to a character array  char[] arr = s.ToCharArray();  // Perform a left rotation within each cycle  for (int i = 0; i < cycles; i++) {    // Start element of the current cycle  char temp = arr[i];  int j = i;  while (true) {  int k = (j + d) % n;  if (k == i)  break;  // Move the element to the next index  arr[j] = arr[k];  j = k;  }  // Place the saved element in the last position  // of the cycle  arr[j] = temp;  }  // Convert the character array back to a string  return new string(arr);  }  static void Main() {  string s = 'GeeksforGeeks';  int d = 2;  string rotatedString = rotateString(s d);  Console.WriteLine(rotatedString);  } }
JavaScript 
// JavaScript Program to left rotate the string by d  // positions using Juggling Algorithm function gcd(a b) {  while (b !== 0) {  let temp = b;  b = a % b;  a = temp;  }  return a; } function rotateString(s d) {  let n = s.length;  // Handle the case where d > size of the string  d %= n;  // Calculate the number of cycles (GCD of n and d)  let cycles = gcd(n d);  // Convert string to a character array  let arr = s.split('');  // Perform a left rotation within each cycle  for (let i = 0; i < cycles; i++) {    // Start element of the current cycle  let temp = arr[i];  let j = i;  while (true) {  let k = (j + d) % n;  if (k === i) {  break;  }  // Move the element to the next index  arr[j] = arr[k];  j = k;  }  // Place the first element in the last position   // of the cycle  arr[j] = temp;  }  // Convert the character array back to a string   return arr.join(''); } let s = 'GeeksforGeeks'; let d = 2; let rotatedString = rotateString(s d); console.log(rotatedString);

出力 
eksforGeeksGe

時間計算量:  の上）
補助スペース: 文字列が次の場合は O(1) 可変 C++ のように。のために 不変文字列 Java C# Python や Javascript と同様に、サイズ n の追加の文字配列が使用されるため、空間複雑度は O(n) になります。

【想定されるアプローチ-2】リバーサルアルゴリズムの利用

このアイデアは、文字列を左に回転すると、 d 最後に配置する (n – d) 要素は先頭と最初に配置されます d 要素は最後になります。

  • 逆行する を含む部分文字列 最初の日 文字列の要素。
  • 逆行する を含む部分文字列 最後 (n – d) 文字列の要素。
  • ついに すべての要素を反転します 文字列の。
C++ 
// C++ program to left rotate a string by d position // using Reversal Algorithm #include    #include  #include    using namespace std; void rotateString(string &s int d) {  int n = s.size();  // Handle the case where d > size of array  d %= n;  // Reverse the first d elements  reverse(s.begin() s.begin() + d);  // Reverse the remaining n-d elements  reverse(s.begin() + d s.end());  // Reverse the entire string  reverse(s.begin() s.end()); } int main() {  string s = 'GeeksforGeeks';  int d = 2;  rotateString(s d);  cout << s << endl;  return 0; }
Java 
// Java program to left rotate a string by d position // using Reversal Algorithm import java.io.*; class GfG {  static String rotateString(String s int d) {  int n = s.length();  // Handle the case where d > size of string  d %= n;  // Convert string to a character array  char[] temp = s.toCharArray();  // Reverse the first d elements  reverse(temp 0 d - 1);  // Reverse the remaining n-d elements  reverse(temp d n - 1);  // Reverse the entire array  reverse(temp 0 n - 1);  // Convert the array back to a string and return  return new String(temp);  }  static void reverse(char[] temp int start int end) {  while (start < end) {  char c = temp[start];  temp[start] = temp[end];  temp[end] = c;  start++;  end--;  }  }  public static void main(String[] args) {  String s = 'GeeksforGeeks';  int d = 2;  String rotatedString = rotateString(s d);  System.out.println(rotatedString);  } }
Python 
# Python program to left rotate a string by d positons # using Reversal Algorithm def rotateString(s d): n = len(s) # Handle cases where d > n d %= n # Convert the string to a list of characters temp = list(s) # Reverse the first d elements reverse(temp 0 d - 1) # Reverse the remaining n - d elements reverse(temp d n - 1) # Reverse the entire array reverse(temp 0 n - 1) # Convert the list back to a string and return return ''.join(temp) def reverse(temp start end): while start < end: temp[start] temp[end] = temp[end] temp[start] start += 1 end -= 1 s = 'GeeksforGeeks' d = 2 rotatedString = rotateString(s d) print(rotatedString)
C# 
// C++ program to left rotate a string by d positions // using Reversal Algorithm using System; class GfG {  static string RotateString(string s int d) {  int n = s.Length;  // Handle cases where d > n  d %= n;  // Convert the string to a character array  char[] temp = s.ToCharArray();  // Reverse the first d elements  Reverse(temp 0 d - 1);  // Reverse the remaining n - d elements  Reverse(temp d n - 1);  // Reverse the entire array  Reverse(temp 0 n - 1);  // Convert the character array back to a string  return new string(temp);  }  static void Reverse(char[] temp int start int end) {  while (start < end) {  char c = temp[start];  temp[start] = temp[end];  temp[end] = c;  start++;  end--;  }  }  static void Main() {  string s = 'GeeksforGeeks';  int d = 2;  string rotatedString = RotateString(s d);  Console.WriteLine(rotatedString);  } }
JavaScript 
// C++ program to left rotate a string by d position // using Reversal Algorithm function rotateString(s d) {  const n = s.length;  // Handle cases where d > n  d %= n;  // Convert the string to a character array  let temp = s.split('');  // Reverse the first d elements  reverse(temp 0 d - 1);  // Reverse the remaining n - d elements  reverse(temp d n - 1);  // Reverse the entire array  reverse(temp 0 n - 1);  // Convert the array back to a string  return temp.join(''); }   function reverse(temp start end) {  while (start < end) {    // Swap elements  [temp[start] temp[end]]   = [temp[end] temp[start]];  start++;  end--;  } } let s = 'GeeksforGeeks'; let d = 2; let rotatedString = rotateString(s d); console.log(rotatedString);

出力 
eksforGeeksGe

時間計算量: O(n) ここで、n は指定された文字列のサイズです。
補助スペース: 文字列が次の場合は O(1) 可変 C++ のように。のために 不変文字列 Java C# Python や Javascript と同様に、サイズ n の追加の文字配列が使用されるため、空間複雑度は O(n) になります。

クイズの作成