Рубрики

Учитывая отсортированный словарь иностранного языка, найдите порядок символов

Учитывая отсортированный словарь (массив слов) иностранного языка, найдите порядок символов в языке.

Примеры:

Input:  words[] = {"baa", "abcd", "abca", "cab", "cad"}
Output: Order of characters is 'b', 'd', 'a', 'c'
Note that words are sorted and in the given language "baa" 
comes before "abcd", therefore 'b' is before 'a' in output.
Similarly we can find other orders.

Input:  words[] = {"caa", "aaa", "aab"}
Output: Order of characters is 'c', 'a', 'b'

Идея состоит в том, чтобы создать граф символов, а затем найти топологическую сортировку созданного графа. Ниже приведены подробные шаги.

1) Создайте граф g с количеством вершин, равным размеру алфавита в данном иностранном языке. Например, если размер алфавита 5, то в словах может быть 5 символов. Изначально в графе нет ребер.

2) Выполните следующие действия для каждой пары смежных слов в данном отсортированном массиве.
… ..A) Пусть текущая пара слов будет word1 и word2 . Один за другим сравните символы обоих слов и найдите первые несовпадающие символы.
… ..b) Создать край в г из несовпадающих характер word1 к тому , что из word2.

3) Распечатать топологическую сортировку созданного выше графика.

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

C ++

// C ++ программа для упорядочивания символов на иностранном языке
#include<iostream>
#include <list>
#include <stack>
#include <cstring>

using namespace std;

  
// Класс для представления графика

class Graph

{

    int V;    // Количество вершин

  

    // Указатель на массив, содержащий списки смежности

    list<int> *adj;

  

    // Функция, используемая topologicalSort

    void topologicalSortUtil(int v, bool visited[], stack<int> &Stack);

public:

    Graph(int V);   // Конструктор

  

    // функция для добавления ребра на график

    void addEdge(int v, int w);

  

    // выводит топологическую сортировку полного графа

    void topologicalSort();

};

  

Graph::Graph(int V)

{

    this->V = V;

    adj = new list<int>[V];

}

  

void Graph::addEdge(int v, int w)

{

    adj[v].push_back(w); // Добавить w в список v.

}

  
// Рекурсивная функция, используемая topologicalSort

void Graph::topologicalSortUtil(int v, bool visited[], stack<int> &Stack)

{

    // Пометить текущий узел как посещенный.

    visited[v] = true;

  

    // Повторение для всех вершин, смежных с этой вершиной

    list<int>::iterator i;

    for (i = adj[v].begin(); i != adj[v].end(); ++i)

        if (!visited[*i])

            topologicalSortUtil(*i, visited, Stack);

  

    // Вставляем текущую вершину в стек, в котором хранится результат

    Stack.push(v);

}

  
// Функция для топологической сортировки. Он использует рекурсивный topologicalSortUtil ()

void Graph::topologicalSort()

{

    stack<int> Stack;

  

    // Пометить все вершины как не посещенные

    bool *visited = new bool[V];

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

        visited[i] = false;

  

    // Вызов рекурсивной вспомогательной функции для сохранения топологической сортировки

    // начиная со всех вершин по одной

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

        if (visited[i] == false)

            topologicalSortUtil(i, visited, Stack);

  

    // Распечатать содержимое стека

    while (Stack.empty() == false)

    {

        cout << (char) ('a' + Stack.top()) << " ";

        Stack.pop();

    }

}

  

int min(int x, int y)

{

    return (x < y)? x : y;

}

  
// Эта функция находит и печатает порядок символов из отсортированного
// массив слов. n - размер слова []. альфа множество возможных
// алфавиты.
// Для простоты эта функция написана так, что только
// первые «альфа» символы могут быть в массиве слов. За
// пример, если альфа равна 7, тогда слова [] должны иметь только «a», «b»,
// 'c' 'd', 'e', 'f', 'g'

void printOrder(string words[], int n, int alpha)

{

    // Создать график с ребрами aplha

    Graph g(alpha);

  

    // Обрабатываем все смежные пары слов и создаем граф

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

    {

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

        // персонаж

        string word1 = words[i], word2 = words[i+1];

        for (int j = 0; j < min(word1.length(), word2.length()); j++)

        {

            // Если мы находим несоответствующий символ, то добавляем ребро

            // от символа word1 к символу word2

            if (word1[j] != word2[j])

            {

                g.addEdge(word1[j]-'a', word2[j]-'a');

                break;

            }

        }

    }

  

    // Печать топологического вида созданного выше графа

    g.topologicalSort();

}

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

int main()

{

    string words[] = {"caa", "aaa", "aab"};

    printOrder(words, 3, 3);

    return 0;

}

Джава

// Java-программа на заказ
// символы на иностранном языке

import java.util.*;

  
// Класс для представления графика

class Graph

{

  

    // Массив, представляющий граф в виде списка смежности

    private final LinkedList<Integer>[] adjacencyList;

  

    Graph(int nVertices)

    {

        adjacencyList = new LinkedList[nVertices];

        for (int vertexIndex = 0; vertexIndex < nVertices; vertexIndex++)

        {

            adjacencyList[vertexIndex] = new LinkedList<>();

        }

    }

  

    // функция для добавления ребра на график

    void addEdge(int startVertex, int endVertex)

    {

        adjacencyList[startVertex].add(endVertex);

    }

  

    private int getNoOfVertices()

    {

        return adjacencyList.length;

    }

  

    // Рекурсивная функция, используемая topologicalSort

    private void topologicalSortUtil(int currentVertex, boolean[] visited,

                                     Stack<Integer> stack)

    {

        // Пометить текущий узел как посещенный.

        visited[currentVertex] = true;

  

        // Повторение для всех вершин, смежных с этой вершиной

        for (int adjacentVertex : adjacencyList[currentVertex])

        {

            if (!visited[adjacentVertex])

            {

                topologicalSortUtil(adjacentVertex, visited, stack);

            }

        }

  

        // Вставляем текущую вершину в стек, в котором хранится результат

        stack.push(currentVertex);

    }

  

    // выводит топологическую сортировку полного графа

    void topologicalSort()

    {

        Stack<Integer> stack = new Stack<>();

  

        // Пометить все вершины как не посещенные

        boolean[] visited = new boolean[getNoOfVertices()];

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

        {

            visited[i] = false;

        }

  

        // Вызываем рекурсивную вспомогательную функцию для хранения топологии

        // Сортировка, начиная со всех вершин по одной

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

        {

            if (!visited[i])

            {

                topologicalSortUtil(i, visited, stack);

            }

        }

  

        // Распечатать содержимое стека

        while (!stack.isEmpty())

        {

            System.out.print((char)('a' + stack.pop()) + " ");

        }

    }

}

  

public class OrderOfCharacters

{

    // Эта функция ищет и печатает порядок

    // персонажа из отсортированного массива слов.

    // альфа это количество возможных алфавитов

    // начиная с 'а'. Для простоты это

    // функция написана так, что только

    // первые символы «альфа» могут быть там

    // в массиве слов. Например, если альфа

    // равно 7, тогда слова [] должны содержать слова

    // имея только 'a', 'b', 'c' 'd', 'e', 'f', 'g'

    private static void printOrder(String[] words, int alpha)

    {

        // Создать график с ребрами aplha

        Graph graph = new Graph(alpha);

  

        for (int i = 0; i < words.length - 1; i++)

        {

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

            // персонаж

            String word1 = words[i];

            String word2 = words[i+1];

            for (int j = 0; j < Math.min(word1.length(), word2.length()); j++)

            {

                // Если мы находим несоответствующий символ, то добавляем ребро

                // от символа word1 к символу word2

                if (word1.charAt(j) != word2.charAt(j))

                {

                    graph.addEdge(word1.charAt(j) - 'a', word2.charAt(j)- 'a');

                    break;

                }

            }

        }

  

        // Печать топологического вида созданного выше графа

        graph.topologicalSort();

    }

  

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

    public static void main(String[] args)

    {

        String[] words = {"caa", "aaa", "aab"};

        printOrder(words, 3);

    }

}

  
// Харикришнан Раджан


Выход:

c a b

Сложность времени: первый шаг для создания графика занимает время O (n + alhpa), где n — количество заданных слов, а alpha — количество символов в данном алфавите. Вторым этапом является также топологическая сортировка. Обратите внимание, что в графе будут альфа- вершины и самое большее (n-1) ребер. Временная сложность топологической сортировки составляет O (V + E), которая здесь составляет O (n + aplha). Таким образом, общая временная сложность составляет O (n + aplha) + O (n + aplha), что составляет O (n + aplha).

Упражнение:
Приведенный выше код не работает, когда ввод недопустим. Например, {«aba», «bba», «aaa»} недопустимы, потому что из первых двух слов мы можем вывести «a», которое должно появляться перед «b», но из последних двух слов мы можем вывести «b» должен появиться перед «а», что невозможно. Расширьте вышеуказанную программу для обработки недопустимых входных данных и сгенерируйте выходные данные как «Недействительно»

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

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

Учитывая отсортированный словарь иностранного языка, найдите порядок символов

0.00 (0%) 0 votes