TCHS-5-500

Problem Statement

A sentence is composed of words, spaces and punctuation. For this problem, words are maximal contiguous strings of letters. Given a sentence, sort the words in the sentence while preserving the spaces and punctuation. Sorting is case sensitive, so uppercase letters precede lowercase letters. Return the newly constructed sentence.

Example: "The big, brown dog ran down the street!"

Returns: "The big, brown dog down ran street the!"

Observe the space and punctuation preservation between the original sentence and the resulting sentence.

Definition

Class:	SuperSort
Method:	wordSort
Parameters:	String
Returns:	String
Method signature:	String wordSort(String sentence)
(be sure your method is public)

Notes

-

Watch out for multiple consecutive spaces (they should be preserved).

Constraints

-

sentence will contain between 1 and 50 characters, inclusive.

-

Each character in sentence will be either a letter ('a'-'z', 'A'-'Z'), ' ', '.', ',', '!' or '?'.

Examples

0)

"The big, brown dog ran down the street!"

Returns: "The big, brown dog down ran street the!"

1)

"This is the first sentence of the paragraph."

Returns: "This first is of paragraph sentence the the."

2)

"t.d,a!f?g.b,q!i?p.h,s!u?m.l,e!v?y.c,j!w?k.n,x!o?r."

Returns: "a.b,c!d?e.f,g!h?i.j,k!l?m.n,o!p?q.r,s!t?u.v,w!x?y."

3)

"What is this?"

Returns: "What is this?"

4)

"? . , ! "

Returns: "? . , ! "

5)

" "

Returns: " "

6)

"faecdb"

Returns: "faecdb"

7)

"a A b B c C d D e E"

Returns: "A B C D E a b c d e"

import java.util.*;

public class SuperSort {

	public static String wordSort(String sent) {
		LinkedList<String> words = new LinkedList<String>();
		Map<Integer, String> tokens = new HashMap<Integer, String>();
		int n = sent.length(), count = 0;
		for (int s = 0, t = 0; s < n;) {
			for (s = t; t < n && Character.isLetter(sent.charAt(t)); t++) ;
			if (t > s) {
				words.add(sent.substring(s, t));
				count++;
			}
			for (s = t; t < n && !Character.isLetter(sent.charAt(t)); t++) ;
			if (t > s)
				tokens.put(count++, sent.substring(s, t));
		}
		Collections.sort(words);
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < count; i++)
			sb.append(tokens.containsKey(i) ? tokens.get(i) : words.poll());
		return sb.toString();
	}

}