Рубрики

Распечатать все возможные строки, которые можно сделать, поместив пробелы

Для данной строки вам нужно вывести все возможные строки, которые можно сделать, поместив между ними пробелы (ноль или единицу).

Input:  str[] = "ABC"
Output: ABC
        AB C
        A BC
        A B C

Источник: Amazon Интервью Опыт | Установите 158, Раунд 1, Q 1.

Идея состоит в том, чтобы использовать рекурсию и создать буфер, который по очереди содержит все выходные строки, имеющие пробелы. Мы постоянно обновляем буфер при каждом рекурсивном вызове. Если длина данной строки равна n, наша обновленная строка может иметь максимальную длину n + (n-1), то есть 2n-1. Таким образом, мы создаем размер буфера 2n (один дополнительный символ для завершения строки).
Мы оставляем 1-й символ как есть, начиная со 2-го символа, мы можем заполнить пробел или символ. Таким образом, можно написать рекурсивную функцию, как показано ниже.

C / C ++

// C ++ программа для печати перестановок заданной строки с пробелами.
#include <iostream>
#include <cstring>

using namespace std;

  
/ * Функция рекурсивно печатает строки, имеющие пробел.

   i и j - индексы в 'str []' и 'buff []' соответственно * /

void printPatternUtil(char str[], char buff[], int i, int j, int n)

{

    if (i==n)

    {

        buff[j] = '\0';

        cout << buff << endl;

        return;

    }

  

    // Либо поставить символ

    buff[j] = str[i];

    printPatternUtil(str, buff, i+1, j+1, n);

  

    // Или поставить пробел, за которым следует следующий символ

    buff[j] = ' ';

    buff[j+1] = str[i];

  

    printPatternUtil(str, buff, i+1, j+2, n);

}

  
// Эта функция создает buf [] для хранения отдельной выходной строки и использует
// printPatternUtil () для печати всех перестановок.

void printPattern(char *str)

{

    int n = strlen(str);

  

    // Буфер для хранения строки, содержащей пробелы

    char buf[2*n]; // 2n-1 символов и 1 строковый терминатор

  

    // Копируем первый символ как есть, так как он будет всегда

    // на первой позиции

    buf[0] = str[0];

  

    printPatternUtil(str, buf, 1, 1, n);

}

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

int main()

{

    char *str = "ABCD";

    printPattern(str);

    return 0;

}

Джава

// Java-программа для печати перестановок заданной строки с пробелами

import java.io.*;

  

class Permutation

{

    // Функция рекурсивно печатает строки, имеющие пробел

    // i и j - индексы в «String str» и «buf []» соответственно

    static void printPatternUtil(String str, char buf[], int i, int j, int n)

    {

        if(i == n)

        {

            buf[j] = '\0';

            System.out.println(buf);

            return;

        }

  

        // Либо поставить символ

        buf[j] = str.charAt(i);

        printPatternUtil(str, buf, i+1, j+1, n);

  

        // Или поставить пробел, за которым следует следующий символ

        buf[j] = ' ';

        buf[j+1] = str.charAt(i);

  

        printPatternUtil(str, buf, i+1, j+2, n);

    }

  

    // Функция создает buf [] для хранения отдельной выходной строки и использует

    // printPatternUtil () для печати всех перестановок

    static void printPattern(String str)

    {

        int len = str.length();

  

        // Буфер для хранения строки, содержащей пробелы

        // 2n-1 символов и 1 строковый терминатор

        char[] buf = new char[2*len];

  

        // Копируем первый символ как есть, так как он будет всегда

        // на первой позиции

        buf[0] = str.charAt(0);

        printPatternUtil(str, buf, 1, 1, len);

    }

  

    // Драйвер программы

    public static void main (String[] args) 

    {

        String str = "ABCD";

        printPattern(str);

    }

}

питон

# Программа Python для печати перестановок заданной строки с
# пробелы.

  
# Вспомогательная функция

def toString(List):

    s = ""

    for x in List:

        if x == '\0':

            break

        s += x

    return s

  
# Функция рекурсивно печатает строки, имеющие пробел.
# i и j - индексы в 'str []' и 'buff []' соответственно

def printPatternUtil(string, buff, i, j, n):

    if i == n:

        buff[j] = '\0'

        print toString(buff)

        return

  

    # Либо поставить персонажа

    buff[j] = string[i]

    printPatternUtil(string, buff, i+1, j+1, n)

  

    # Или поставить пробел, за которым следует следующий символ

    buff[j] = ' '

    buff[j+1] = string[i]

  

    printPatternUtil(string, buff, i+1, j+2, n)

  
# Эта функция создает buf [] для хранения отдельной выходной строки
# и использует printPatternUtil () для печати всех перестановок.

def printPattern(string):

    n = len(string)

  

    # Буфер для хранения строки, содержащей пробелы

    buff = [0] * (2*n) # 2n-1 символов и 1 символ конца строки

  

    # Скопируйте первый символ как есть, так как он будет всегда

    # на первой позиции

    buff[0] = string[0]

  

    printPatternUtil(string, buff, 1, 1, n)

  
# Драйверная программа

string = "ABCD"

printPattern(string)

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

C #

// C # программа для печати перестановок
// заданная строка с пробелами

using System;

  

class GFG {

      

    // Функция рекурсивно печатает

    // строки, имеющие пробел

    // i и j являются индексами в 'String

    // str 'и' buf [] 'соответственно

    static void printPatternUtil(string str, 

             char []buf, int i, int j, int n)

    {

        if(i == n)

        {

            buf[j] = '\0';

            Console.WriteLine(buf);

            return;

        }

  

        // Либо поставить символ

        buf[j] = str[i];

        printPatternUtil(str, buf, i+1, j+1, n);

  

        // Или поставить пробел с последующим

        // персонаж

        buf[j] = ' ';

        buf[j+1] = str[i];

  

        printPatternUtil(str, buf, i+1, j+2, n);

    }

  

    // Функция создает buf [] для хранения

    // индивидуальная строка вывода и использует

    // printPatternUtil () чтобы напечатать все

    // перестановки

    static void printPattern(string str)

    {

        int len = str.Length;

  

        // Буфер для хранения строки, содержащей

        // пробелы 2n-1 символов и 1 строка

        // терминатор

        char []buf = new char[2*len];

  

        // Копируем первый символ как есть,

        // так как сначала будет всегда

        // позиция

        buf[0] = str[0];

        printPatternUtil(str, buf, 1, 1, len);

    }

  

    // Драйвер программы

    public static void Main () 

    {

        string str = "ABCD";

        printPattern(str);

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// PHP-программа для печати перестановок
// данной строки с пробелами.

  
/ * Функция рекурсивно печатает строки
с космическим рисунком. я и j - индексы
в 'str []' и 'buff []' соответственно * /

function printPatternUtil($str, $buff, $i, $j, $n)

{

    if ($i == $n)

    {

        $buff[$j] = '';

        echo str_replace(',','',implode(',', $buff))."\n";

        return;

    }

  

    // Либо поставить символ

    $buff[$j] = $str[$i];

    printPatternUtil($str, $buff, $i + 1, $j + 1, $n);

  

    // Или поставить пробел, за которым следует следующий символ

    $buff[$j] = ' ';

    $buff[$j+1] = $str[$i];

  

    printPatternUtil($str, $buff, $i +1 , $j + 2, $n);

}

  
// Эта функция создает buf [] для хранения
// индивидуальная строка вывода и использует
// printPatternUtil () для печати всех перестановок.

function printPattern($str)

{

    $n = strlen($str);

  

    // Буфер для хранения строки, содержащей пробелы

    // 2n-1 символов и 1 строковый терминатор

    $buf = array_fill(0, 2 * $n, null); 

  

    // Копируем первый символ как есть, так как он будет всегда

    // на первой позиции

    $buf[0] = $str[0];

  

    printPatternUtil($str, $buf, 1, 1, $n);

}

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

$str = "ABCD";

printPattern($str);

      
// Этот код предоставлен chandan_jnu
?>


Выход:

ABCD
ABC D
AB CD
AB C D
A BCD
A BC D
A B CD
A B C D 

Сложность времени: поскольку число разрывов равно n-1, имеется всего 2 ^ (n-1) скороговорок, каждая из которых имеет длину в диапазоне от n до 2n-1. Таким образом, общая сложность будет O (n * (2 ^ n)).

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

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

Распечатать все возможные строки, которые можно сделать, поместив пробелы

0.00 (0%) 0 votes