Given a jumbled sentence as a list of strings, the task is to print the sorted sentence of strings on basis of the presence of a single integer in every string. If two string has the same integer sort them lexicographically.
Examples:
Input : {"2a", "grea3t", "l3earning", "neveropenfor0neveropen", "p10latform", "is1"}
Output: neveropenfor0neveropen is1 2a grea3t l3earning p10latform
Explanation: Since order of integer parts are: 0, 1, 2, 3, 3, 10
therefore the order of string must be:
neveropenfor0neveropen, is1, 2a, grea3t, l3earning, p10latform.
Input : {"love9", "i8s", "In5dia"}
Output: In5dia i8s love9
Approach 1: The problem can be solved using greedy algorithm. we will create a list of pairs, the first value of pairs will hold the integer part of the string and the second value of pairs will hold string as it is and then we will sort this list of pairs in ascending order so that the string having lower-valued integer will earlier in list. follow the steps below to solve the problem:
- Create a list of pairs say A, in pair 1st values, will be an integer in string and 2nd value will be a string as it is.
- Sort A in increasing order.
- Iterate over every pair of A and print the 2nd value of the pair.
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Method 1// To sort jumbled list void sortJumbledList(string jumbled[], int size){ // Initializing a list to store pairs multimap<int, string> ans; // Iterating over JumbledList for (int i = 0; i < size; i++) { string temp = jumbled[i]; // Finding integer part int number = 0; for (int j = 0; j < temp.size(); j++) { if (temp[j] >= '0' && temp[j] <= '9') { number *= 10; number += (temp[j] - '0'); } } // Appending pairs ans.insert(pair<int, string>(number, jumbled[i])); } // Printing the sorted word of the string for (auto i : ans) { cout << i.second << " "; }}// Method 2// Main driver codeint main(){ // Custom input string string JumbledList[] = { "2a", "grea3t", "l3earning", "neveropenfor0neveropen", "p5latform", "is1" }; // Calling method 1 inside main() method sortJumbledList(JumbledList, 6); return 0;} |
Java
//Java program for above approach import java.util.*;public class JumbledListSort { // Method 1 // To sort jumbled list public static void sortJumbledList(String jumbled[], int size) { // Initializing a list to store pairs Map<Integer, String> ans = new TreeMap<>(); // Iterating over JumbledList for (int i = 0; i < size; i++) { String temp = jumbled[i]; // Finding integer part int number = 0; for (int j = 0; j < temp.length(); j++) { if (Character.isDigit(temp.charAt(j))) { number *= 10; number += (temp.charAt(j) - '0'); } } // Appending pairs ans.put(number, jumbled[i]); } // Printing the sorted word of the string for (Map.Entry<Integer, String> entry : ans.entrySet()) { System.out.print(entry.getValue() + " "); } } // Method 2 // Main driver code public static void main(String[] args) { // Custom input string String JumbledList[] = { "2a", "grea3t", "l3earning", "neveropenfor0neveropen", "p5latform", "is1" }; // Calling method 1 inside main() method sortJumbledList(JumbledList, 6); }}//Contributed by adityashae15 |
Python3
# Python program for above approachdef SortJumbledList(JumbledList): # Initializing a list to store pairs A = [] # Iterating over JumbledList for string in JumbledList: # Finding integer part integer = [] for j in string: if j in {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'}: integer.append(j) integer = ''.join(integer) # Appending pairs A.append((integer, string)) # Sorting the list of pairs A.sort() # Printing sorted word of the string for integer, string in A: print(string, end=' ')# Driver CodeJumbledList = ["2a", "grea3t", "l3earning", "neveropenfor0neveropen", "p5latform", "is1"]# Function CallSortJumbledList(JumbledList) |
C#
//C# program for above approachusing System;using System.Collections.Generic;public class JumbledListSort { // Method 1 // To sort jumbled list public static void sortJumbledList(string[] jumbled, int size) { // Initializing a dictionary to store pairs SortedDictionary<int, string> ans = new SortedDictionary<int, string>(); // Iterating over JumbledList for (int i = 0; i < size; i++) { string temp = jumbled[i]; // Finding integer part int number = 0; for (int j = 0; j < temp.Length; j++) { if (Char.IsDigit(temp[j])) { number *= 10; number += (temp[j] - '0'); } } // Adding key-value pair to the dictionary if (ans.ContainsKey(number)) { int index = 1; while (ans.ContainsKey(number + index)) { index++; } ans.Add(number + index, jumbled[i]); } else { ans.Add(number, jumbled[i]); } } // Printing the sorted word of the string foreach (KeyValuePair<int, string> entry in ans) { Console.Write(entry.Value + " "); } } // Method 2 // Main driver code public static void Main() { // Custom input string string[] JumbledList = { "2a", "grea3t", "l3earning", "neveropenfor0neveropen", "p5latform", "is1" }; // Calling method 1 inside Main() method sortJumbledList(JumbledList, 6); }}//Contributed by rishabmalhdijo |
Javascript
// Method 1// To sort jumbled list function sortJumbledList(jumbled, size) { // Initializing a map to store pairs let ans = new Map(); // Iterating over JumbledList for (let i = 0; i < size; i++) { let temp = jumbled[i]; // Finding integer part let number = 0; for (let j = 0; j < temp.length; j++) { if (temp[j] >= '0' && temp[j] <= '9') { number *= 10; number += (temp.charCodeAt(j) - '0'.charCodeAt(0)); } } // Appending pairs ans.set(number, jumbled[i]); } // Printing the sorted word of the string for (let [key, value] of ans) { console.log(value + " "); }}// Method 2// Main driver codefunction main() { // Custom input string let JumbledList = [ "2a", "grea3t", "l3earning", "neveropenfor0neveropen", "p5latform", "is1" ]; // Calling method 1 inside main() method sortJumbledList(JumbledList, JumbledList.length);}main(); |
Output
neveropenfor0neveropen is1 2a grea3t l3earning p5latform
Time Complexity: O(N*M*log(N)), where N is the length of JumbledList and M is the string length. (N*log(N) for sorting/multimap.)
Auxiliary Space: O(N*M)
Approach 2: We can use a dictionary to store the index of the string while iterating through the JumbledList, where the key will be string and value will be index(one can also use string as value and index as key).
- Create a dictionary/Hashmap as mentioned above.
- Create an empty list namely of the size of the original JumbledList.
- Iterate over dictionary items and assign strings(keys) to index(values) in the above-created list.
C++
// C++ program for above approach#include <bits/stdc++.h>#include <string>using namespace std;void sortJumbledList(string jumbled[], int size){ // Initializing a list to store pairs unordered_map<string, int> mp; // Iterating over JumbledList for (int i = 0; i < size; i++) { string temp = jumbled[i]; // Storing the integer part for (int j = 0; j < temp.size(); j++) { if (temp[j] >= '0' && temp[j] <= '9') { mp[temp] = temp[j] - '0'; } } } // Creating an empty array to store answer string ordered[size] = {}; // Iterating over map to assign string to appropriate // indices for (const auto& p : mp) { string word = p.first; int index = p.second; ordered[index] = word; } for (const auto& word : ordered) { cout << word << " "; }}// Driver codeint main(){ string JumbledList[] = { "2a", "grea3t", "l3earning", "neveropenfor0neveropen", "p5latform", "is1" }; sortJumbledList(JumbledList, 6); return 0;} |
Java
import java.util.*;public class Main { public static void SortJumbledList(String[] JumbledList) { // A dictionary to store strings as key and value as its index Map<String, Integer> d = new HashMap<>(); // Iterating over JumbledList for (String string : JumbledList) { // Iterating over characters in string to find digits as its index for (char ch : string.toCharArray()) { //Storing strings index if (Character.isDigit(ch)) { d.put(string, Character.getNumericValue(ch)); } } } // ist to store all words in order String[] orderedList = new String[JumbledList.length]; // Storing strings at required index for (Map.Entry<String, Integer> entry : d.entrySet()) { orderedList[entry.getValue()] = entry.getKey(); } // Neat way to print list elements as space separated elements System.out.println(String.join(" ", orderedList)); } // Driver Code public static void main(String[] args) { String[] JumbledList = {"2a", "grea3t", "l3earning", "neveropenfor0neveropen", "p5latform", "is1"}; // Function Call SortJumbledList(JumbledList); }}// This code is contributed bys shivhack999 |
Python3
def SortJumbledList(JumbledList): # A dictionary to store strings as key and value as its index d = {} # Iterating over JumbledList for string in JumbledList: #Iterating over characters in string to find digits as its index for ch in string: if ch.isdigit(): # Storing strings index d[string]=int(ch) # List to store all words in order orderedList = ['']*len(JumbledList) # Storing strings at required index for string,index in d.items(): orderedList[index]=string # Neat way to print list elements as space separated elements print(*orderedList)# Driver CodeJumbledList = [ "2a", "grea3t", \ "l3earning", \ "neveropenfor0neveropen", \ "p5latform", "is1" ] # Function CallSortJumbledList(JumbledList) |
C#
using System;using System.Collections.Generic;class Program{ static void SortJumbledList(string[] jumbled) { // Initializing a dictionary to store pairs Dictionary<string, int> mp = new Dictionary<string, int>(); // Iterating over JumbledList for (int i = 0; i < jumbled.Length; i++) { string temp = jumbled[i]; // Storing the integer part foreach (char c in temp) { if (char.IsDigit(c)) { mp[temp] = int.Parse(c.ToString()); } } } // Creating an empty array to store the ordered result string[] ordered = new string[jumbled.Length]; // Iterating over the dictionary to assign strings to appropriate indices foreach (var kvp in mp) { string word = kvp.Key; int index = kvp.Value; ordered[index] = word; } // Printing the sorted list foreach (string word in ordered) { Console.Write(word + " "); } } static void Main(string[] args) { string[] jumbledList = { "2a", "grea3t", "l3earning", "neveropenfor0neveropen", "p5latform", "is1" }; SortJumbledList(jumbledList); }} |
Javascript
// Javascript code for the above approachfunction SortJumbledList(JumbledList) { // A dictionary to store strings as key and value as its index const d = {}; // Iterating over JumbledList for (const string of JumbledList) { //Iterating over characters in string to find digits as its index for (const ch of string) { if (ch >= '0' && ch <= '9') { // Storing strings index d[string] = parseInt(ch); } } } // List to store all words in order const orderedList = new Array(JumbledList.length).fill(''); // Storing strings at required index for (const [string, index] of Object.entries(d)) { orderedList[index] = string; } // Neat way to print list elements as space separated elements console.log(...orderedList);}// Driver Codeconst JumbledList = ["2a", "grea3t", "l3earning", "neveropenfor0neveropen", "p5latform", "is1"];// Function CallSortJumbledList(JumbledList);// This code is contributed by princekumaras |
Output
neveropenfor0neveropen is1 2a l3earning p5latform
Time Complexity: O(N*M), where N is the length of JumbledList and M is the string length.
Auxiliary Space: O(N*M)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
