C++ program: rearrange the position of words in alphabetical order

In this problem, a string is given as input and we have to sort the words appearing in the string in lexicographic order. To do this, we assign an index starting from 1 to each word in the string (separated by spaces) and obtain the output as a sorted index.

String = {“Hello”, “World”}
“Hello” = 1
“World” = 2

Since the words in the input string have been arranged in lexicographic order, the output will be printed as "1 2".

Let’s look at some input/result scenarios -

Assuming all words in the input string are the same, let’s see the results -

Input: {“hello”, “hello”, “hello”}
Result: 3

The result obtained will be the last position of the word.

Now let us consider an input string containing words starting with the same letter, the resulting output will be based on the subsequent letters of the starting letter.

Input: {“Title”, “Tutorial”, “Truth”}
Result: 1 3 2

Another common input scenario for this method and the results obtained are as follows -

Input: {“Welcome”, “To”, “Tutorialspoint”}
Result: 2 3 1

Note - The positions returned are the original positions of these words in the input string. These numbers don't change once the words are sorted within the method.

algorithm

• This method is performed using the vector and map abstract data types.

• Use an automatic iterator to traverse the input string within the string range.

• Alphabetical swapping of words is done by pushing the elements to the back of the vector data type.

• Once the words are rearranged lexicographically, the original positions of those words in the string are returned as output.

Example

Let us have a string that is ["articles", "point", "world"], and the order of the strings is -

“articles”: 1
“point”: 2
“world”: 3

We can map each string with an index. We can then sort the string and print out the index of the map. We can use a map, a sorted data structure in C, to store key-value pairs. Let's quickly implement our approach.

#include <iostream>
#include <vector>
#include <map>
using namespace std;
vector<int> solve(vector<string>& arr) {
   map<string, int> mp;
   int index = 1;
   for(string s : arr)
      mp[s] = index++;
   vector<int> res;
   for(auto it : mp)
      res.push_back(it.second);
   return res;
}
int main() {
   vector<string> arr = {"articles", "point", "world"};
   vector<int> res = solve(arr);
   for(int i : res) cout << i << " ";
   return 0;
}

Output

1 2 3

Now the reordering of strings will be -

“point,”
“articles,”
“world”

Time complexity - O(n * log n)

Space complexity - O(n)

in conclusion

We use maps to sort and map for us. We can also use a hash map, sort a vector or array, and print the index in the hash map. The time complexity is O(n*log(n)) and the space complexity is O(n).

The above is the detailed content of C++ program: rearrange the position of words in alphabetical order. For more information, please follow other related articles on the PHP Chinese website!