Рубрики

Лексикографически минимальное вращение струны | Комплект 1

Введите код для поиска лексикографического минимума в круговом массиве, например, для массива BCABDADAB лексикографический минимум — ABBCABDAD.

Источник: Google письменный тест

Больше примеров:

Input:  GEEKSQUIZ
Output: EEKSQUIZG

Input:  GFG
Output: FGG

Input:  GEEKSFORGEEKS
Output: EEKSFORGEEKSG

Ниже приводится простое решение. Пусть заданная строка будет 'str'
1) Объедините 'str' с собой и сохраните во временной строке 'concat'.
2) Создайте массив строк для хранения всех вращений 'str'. Пусть массив будет 'arr'.
3) Найти все вращения 'str', взяв подстроки 'concat' с индексом 0, 1, 2..n-1. Храните эти вращения в arr []
4) Сортировать arr [] и вернуть arr [0].

Ниже приводится реализация вышеуказанного решения.

C ++

// Простая программа на C ++ для поиска лексикографически минимального поворота
// данной строки
#include <iostream>
#include <algorithm>

using namespace std;

  
// Этот функционал возвращает лексикографически минимум
// вращение ул
string minLexRotation(string str)
{

    // Найти длину заданной строки

    int n = str.length();

  

    // Создать массив строк для хранения всех вращений

    string arr[n];

  

    // Создаем конкатенацию строки с собой

    string concat = str + str;

  

    // Один за другим сохраняем все вращения str в массиве.

    // Вращение получается путем получения подстроки concat

    for (int i = 0; i < n; i++)

        arr[i] = concat.substr(i, n);

  

    // Сортировка всех вращений

    sort(arr, arr+n);

  

    // Возвращаем первый поворот из отсортированного массива

    return arr[0];

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    cout << minLexRotation("GEEKSFORGEEKS") << endl;

    cout << minLexRotation("GEEKSQUIZ") << endl;

    cout << minLexRotation("BCABDADAB") << endl;

}

Джава

// Простая Java-программа для поиска
// лексикографически минимальное вращение
// данной строки

import java.util.*;

  

class GFG

{

  

    // Эта функция возвращает лексикографически

    // минимальное вращение ул

    static String minLexRotation(String str) 

    {

        // Найти длину заданной строки

        int n = str.length();

  

        // Создать массив строк

        // хранить все вращения

        String arr[] = new String[n];

  

        // Создать конкатенацию

        // Строка с собой

        String concat = str + str;

  

        // Один за другим сохраняем все вращения

        // из строки в массиве. Вращение

        // полученный путем получения подстроки concat

        for (int i = 0; i < n; i++)

        {

            arr[i] = concat.substring(i, i + n);

        }

  

        // Сортировка всех вращений

        Arrays.sort(arr);

  

        // Возвращаем первое вращение

        // из отсортированного массива

        return arr[0];

    }

  

    // Код драйвера

    public static void main(String[] args) 

    {

        System.out.println(minLexRotation("GEEKSFORGEEKS"));

        System.out.println(minLexRotation("GEEKSQUIZ"));

        System.out.println(minLexRotation("BCABDADAB"));

    }

}

  
// Этот код предоставлен 29AjayKumar

python3

# Простая программа на Python3 для поиска лексикографически
# минимальное вращение заданной строки

  
# Эта функция возвращает лексикографически минимум
# вращение ул

def minLexRotation(str_) :

  

    # Найти длину заданной строки

    n = len(str_)

  

    # Создать массив строк для хранения всех вращений

    arr = [0] * n

  

    # Создать конкатенацию строки с собой

    concat = str_ + str_

  

    # Один за другим сохраняем все вращения str в массиве.

    # Вращение получается при получении подстроки concat

    for i in range(n) :

        arr[i] = concat[i : n + i]

  

    # Сортировать все вращения

    arr.sort()

  

    # Вернуть первый поворот из отсортированного массива

    return arr[0]

  
Код водителя

print(minLexRotation("GEEKSFORGEEKS"))

print(minLexRotation("GEEKSQUIZ"))

print(minLexRotation("BCABDADAB"))

  
# Этот код предоставлен divyamohan123

C #

// Простая программа на C # для поиска
// лексикографически минимальное вращение
// данной строки

using System;

  

class GFG

{

  

    // Эта функция возвращает лексикографически

    // минимальное вращение ул

    static String minLexRotation(String str) 

    {

        // Найти длину заданной строки

        int n = str.Length;

  

        // Создать массив строк

        // хранить все вращения

        String []arr = new String[n];

  

        // Создать конкатенацию

        // Строка с собой

        String concat = str + str;

  

        // Один за другим сохраняем все вращения

        // из строки в массиве. Вращение

        // полученный путем получения подстроки concat

        for (int i = 0; i < n; i++)

        {

            arr[i] = concat.Substring(i, n);

        }

  

        // Сортировка всех вращений

        Array.Sort(arr);

  

        // Возвращаем первое вращение

        // из отсортированного массива

        return arr[0];

    }

  

    // Код драйвера

    public static void Main(String[] args) 

    {

        Console.WriteLine(minLexRotation("GEEKSFORGEEKS"));

        Console.WriteLine(minLexRotation("GEEKSQUIZ"));

        Console.WriteLine(minLexRotation("BCABDADAB"));

    }

}

  
// Этот код предоставлен Rajput-Ji

Выход:

EEKSFORGEEKSG
EEKSQUIZG
ABBCABDAD

Лексикографически наименьшая повернутая последовательность | Набор 2

Временная сложность вышеуказанного решения составляет O (n 2 Logn) в предположении, что мы использовали алгоритм сортировки O (nLogn).
Эта проблема может быть решена с использованием более эффективных методов, таких как алгоритм Бута, который решает проблему за O (n) времени. Скоро мы расскажем об этих методах в виде отдельных постов.

Эта статья предоставлена Abhishek. Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Лексикографически минимальное вращение струны | Комплект 1

0.00 (0%) 0 votes