CODEWITHSUNDEEP
algorithm
d123
d123

Reputation: 437

Search a word in a given paragraph

You are given a paragraph in which the length of all the words in a line has following properties:

You are given a word, and have to write a code to search it in the given paragraph and return the line number.

Upvotes: 4

Views: 959

Answers (2)

Jens Schwarzer
Jens Schwarzer

Reputation: 2870

There seems to be no requirements to the run-time complexetity - so why not just implement a linear search? Maybe that odd/even thing was just added to confuse you! Keep it simple ;)

Upvotes: -1

amit
amit

Reputation: 178461

If each line is given by a list of words, it is actually two sorted sublists:

(1) list of odd words: sorted increasinly by length
(2) list of even words: sorted decreasingly by length

Use a binary search on both lists, with a comparator accordding to : word.length()
Once you find a match [the word you are looking for and the word in the list you are currently searching] is in the same length: check if it is the same word.

repeat for each line.

Complexity [for each line]: O(logn * |S|) where |S| is the size of your word and n is the number of words in a line.

Upvotes: 7

Related Questions