C++ program: rearrange the position of words in alphabetical order-C++-php.cn

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

Copy after login

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

Copy after login

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

Copy after login

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

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

Copy after login

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

Copy after login

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

Copy after login

Output

1 2 3

Copy after login

Now the reordering of strings will be -

“point,” “articles,” “world”

Copy after login

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!