CODEWITHSUNDEEP
algorithm
Amit
Amit

Reputation: 817

Algorithm to reform a sentence from sentence whose spaces are removed and alphabets of words are reordered?

I was looking around some puzzles online to improve my knowledge on algorithms...

I came upon below question:

"You have a sentence with several words with spaces remove and words having their character order shuffled. You have a dictionary. Write an algorithm to produce the sentence back with spaces and words with normal character order."

I do not know what is good way to solve this.

I am new to algorithms but just looking at problem I think I would make program do what an intellectual mind would do.

Here is something I can think of:

-First find out manually common short english words from dictionary like "is" "the" "if" etc and put in dataset-1.

-Then find out permutation of words in dataset1 (eg "si", "eht" or "eth" or "fi") and put in dataset-2

-then find out from input sentense what character sequence matches the words of dataset2 and put them in dataset-3 and insert space in input sentence instead of those found.

-for rest of the words i would perform permutations to find out word from dictionary.

I am newbie to algorithms...is it a bad solution?

Upvotes: 3

Views: 1401

Answers (2)

Nuclearman
Nuclearman

Reputation: 5314

Actually, might be wise to start by partitioning the dictionary by word length.

Then try to find the largest words that can be made using the letters avaliable, instead of finding the smallest ones. Short words are more common and thus will be harder to narrow down. IE: is it really "If" or "fig".

Then for each word length w, you can proceed w characters at a time.

There are still a lot of possible combinations though, simply because you found a valid word, doesn't mean it's the right word. Once you've gone through all the substrings, of which there should be something like O(c^4*d) where d is the number of words in the dictionary and c is the number of characters in the sentence. Practically speaking if the dictionary is sorted by word length, it'll be a fair bit less than that. Then you have to take the valid words, and figure out an ordering that works, so that all characters are used. There might be multiple solutions.

Upvotes: 0

BenMatok
BenMatok

Reputation: 160

this seems like a perfectly fine solution,

In general there are 2 parameters for judging an algorithm.

  1. correctness - does the algorithm provide the correct answer.

  2. resources - the time or storage size needed to provide an answer.

usually there is a tradeoff between these two parameters.

so for example the size of your dictionary dictates what scrambled sentences you may reconstruct, giving you a correct answer for more inputs, however the whole searching process would take longer and would require more storage.

The hard part of the problem you presented is the fact that you need to compute permutations, and there are a LOT of them.

so checking them all is expensive, a good approach would be to do what you suggested, create a small subset of commonly used words and check them first, that way the average case is better.

note: just saying that you check the permutation/search is ok, but in the end you would need to specify the exact way of doing that.

currently what you wrote is an idea for an algorithm but it would not allow you to take a given input and mechanically work out the output.

Upvotes: 1

Related Questions