“This is the first day of my participation in the First Challenge 2022. For details: First Challenge 2022”

Stable_sort = stable_sort = stable_sort

— Leetcode

preface

Hello, I’m One, welcome to my algorithm channel.

Only do interesting algorithms, only write algorithms for interviews.

Question

1451. Rearrange the words in the sentence

Difficulty: Medium

A “sentence” is a string of words separated by Spaces. Give you a sentence that satisfies the following format:

Each word in a capital text is separated by a single space. Rearrange the words in text so that all the words are in ascending order of length. If two words are of the same length, their relative order in the original sentence is preserved.

Please return the new sentence in the same format as above.

Example:

Input: text = "Keep calm and code on" output: "on and Keep calm code" "And", three letters. The four letters "keep" need to remain in the relative order of the original sentence because there are other words of the same length. "Calm" has four letters. "Code" has four letters.Copy the code
  • textIt starts with a capital letter, then contains several lower case letters and a single space between words.
  • 1 <= text.length <= 10^5

Solution

If two words are of the same length, retain their relative order in the original sentence.

There are two ways to ensure relative order:

  • Use sorting algorithms that do not change the relative order.
  • If we do the sorting before we sort, we don’t care what sort algorithm we use.

Sorting before processing:

The first thing to think about is a hash table, using the length of a character as a key, and the value as a value. Traversal Concatenates two characters if the key already exists. Change value to store value + space to enable sorting again.

Sorting algorithm:

Arrays.sort is one of the things you might think of, but if you look at the source code, you’ll see that the underlying sort changes based on thresholds (the length of the array) to take advantage of the various sorting algorithms. So it’s very unstable.

Finally changed to use the Comparator implementation.

Don’t forget to start with a capital letter.

Code

M1

/ * * *@authorA coding * /
class Solution {
    public String arrangeWords(String text) {
        String[] words = text.toLowerCase().split("");
        Arrays.sort(words, Comparator.comparingInt(String::length));
        words[0] = words[0].substring(0.1).toUpperCase() + words[0].substring(1);;
        return String.join("", words); }}Copy the code

M2

/ * * *@authorA coding * /
 class Solution {
    public String arrangeWords(String text) {
        StringBuilder sb = new StringBuilder();
        Map<Integer, String> map = new HashMap<>();
        // Convert the first letter to lowercase
        text = text.substring(0.1).toLowerCase() + text.substring(1);
        // Add to map
        String[] texts = text.split("");
        for (String s : texts) map.put(s.length(), map.getOrDefault(s.length(), "") + s + "");
        / / traverse the key
        int[] keys = new int[map.size()];
        int idx = 0;
        for (Integer key : map.keySet()) keys[idx++] = key;
        Arrays.sort(keys);
        for (int key : keys) sb.append(map.get(key));
        // Convert the first letter to uppercase
        String res = sb.toString();
        res = res.substring(0.1).toUpperCase() + res.substring(1, res.length() - 1);
        returnres; }}Copy the code

The last

Thumbs up, thumbs up, and fucking thumbs up!