1 Replies - 918 Views - Last Post: 06 March 2013 - 06:10 PM Rate Topic: -----

#1 burakaltr  Icon User is offline

  • D.I.C Regular

Reputation: 91
  • View blog
  • Posts: 274
  • Joined: 07-November 10

One of the Best Algorithms Related to String Manipulation

Posted 06 March 2013 - 05:33 PM

One of the Hardest Thinking is involved in this Problem below, I think.

What Do You Think ?

Thanks !

Quote

Run-length encoding (RLE) is a simple "compression algorithm" (an algorithm which takes a block of data and reduces its size, producing a block that contains the same information in less space). It works by replacing repetitive sequences of identical data items with short "tokens" that represent entire sequences. Applying RLE to a string involves finding sequences in the string where the same character repeats. Each such sequence should be replaced by a "token" consisting of:

the number of characters in the sequence
the repeating character
If a character does not repeat, it should be left alone.

For example, consider the following string:

qwwwwwwwwweeeeerrtyyyyyqqqqwEErTTT
After applying the RLE algorithm, this string is converted into:

q9w5e2rt5y4qw2Er3T
In the compressed string, "9w" represents a sequence of 9 consecutive lowercase "w" characters. "5e" represents 5 consecutive lowercase "e" characters, etc.

Write a program that takes a string as input, compresses it using RLE, and outputs the compressed string. Case matters - uppercase and lowercase characters should be considered distinct. You may assume that there are no digit characters in the input string. There are no other restrictions on the input - it may contain spaces or punctuation. There is no need to treat non-letter characters any differently from letters.


Is This A Good Question/Topic? 0
  • +

Replies To: One of the Best Algorithms Related to String Manipulation

#2 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 1909
  • View blog
  • Posts: 3,954
  • Joined: 11-December 07

Re: One of the Best Algorithms Related to String Manipulation

Posted 06 March 2013 - 06:10 PM

If you are finding it tricky then try these instead of trying to jump straight to the answer:

1. Loop through the characters of the string and print out the character count so far. This should just give you the numbers 1 to the length of the string.

2. Now reset the counter any time the character you are looking at is not the same as the previous one.

3. Now only display the numbers immediately before you reset the counter. Don't display the intermediate results. Be careful to include the first and last numbers!

4. Display the character after the number.

5. Add a condition to avoid displaying 1s.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1