AlgorithmsComputer Science TopicsData StructuresDynamic ProgrammingJavaLeetCode SolutionsMedium DifficultyProgramming InterviewsProgramming LanguagesTreeMapTreesUndirected Graphs

[LeetCode 1451] Rearrange Words in a Sentence

https://leetcode.com/problems/rearrange-words-in-a-sentence/

Given a sentence text (A sentence is a string of space-separated words) in the following format:

• First letter is in upper case.
• Each word in text are separated by a single space.

Your task is to rearrange the words in text such that all words are rearranged in an increasing order of their lengths. If two words have the same length, arrange them in their original order.

Return the new text following the format shown above.

Example 1:

Input: text = "Leetcode is cool"
Output: "Is cool leetcode"
Explanation: There are 3 words, "Leetcode" of length 8, "is" of length 2 and "cool" of length 4.
Output is ordered by length and the new first word starts with capital letter.

Example 2:

Input: text = "Keep calm and code on"
Output: "On and keep calm code"
Explanation: Output is ordered as follows:
"On" 2 letters.
"and" 3 letters.
"keep" 4 letters in case of tie order by position in original text.
"calm" 4 letters.
"code" 4 letters.

Example 3:

Input: text = "To be or not to be"
Output: "To be or to be not"

Constraints:

• text begins with a capital letter and then contains lowercase letters and single space between words.
• 1 <= text.length <= 10^5

Solution

Basic intuition:

• Create a TreeMap, with key Integer and value List<String>. TreeMap to maintain order of keys. Integer key represents length of strings in list.
• Iterate through the list of individual words and add them to the TreeMap
• Loop through the keys in the TreeMap and append all the words to the result string.
public static String arrangeWords(String text) {
Map<Integer, List<String>> map = new TreeMap<>();
String[] arr = text.split(" ");
if (arr.length == 0) {
return text;
}

arr = arr.toLowerCase();
for (String s : arr) {
int len = s.length();
}

StringBuilder sb = new StringBuilder();
for (int i : map.keySet()) {
List<String> ls = map.get(i);
for (String s : ls) {
sb.append(s).append(' ');
}
}

sb.setCharAt(0, Character.toUpperCase(sb.charAt(0)));
sb.deleteCharAt(sb.length() - 1);
return sb.toString();
}

More complex solution:

Intuition is to count the distance between spaces.

public static String arrangeWordsAlt(String text) {
char[] t = text.toCharArray(), s = new char[t.length];
t ^= 32;
List<int[]> A = new ArrayList<>();
for (int i = 0, beg = 0; i <= t.length; i++)
if (i == t.length || t[i] == ' ') {
A.add(new int[] { i - beg, beg });
beg = i + 1;
}
Collections.sort(A, (a, b) -> a == b ? a - b : a - b);
for (int i = 0, j = 0; i < A.size(); i++) {
int len = A.get(i), beg = A.get(i);
while (len-- > 0)
s[j++] = t[beg++];
if (i < A.size() - 1)
s[j++] = ' ';
}
s ^= 32;

Previous Post

Next article

[LeetCode 1557] Minimum Number of Vertices to Reach All Nodes 