Feature #8: Compress File II
Implement the "Compress File II" feature for our "Operating System" project.
We'll cover the following...
Description
The ability to compress files is an essential functionality that can come in handy. In this feature, we will learn how to carry out basic file compression, just like the one that WinZip does. The file compression process will compress text files by replacing multiple consecutive occurrences of the same character with that character followed by the number of its consecutive occurrences. If a character does not have any consecutive repetitions, then we will just write the character to the output. For example, "abbbbccc"
will become "ab4c3"
. Our task will be to return the compressed file using constant additional space.
Note: Suppose that
'a'
repeats 15 times. In that case, we will compress it like this:['a', '1', '5']
We will be provided with a character list that will represent the text in a file.
Solution
We will make changes to the original list and return it as a compressed file because we can only use constant space. Here is the algorithm that we will use:
- Count the continuous occurrences of a character.
- Remove all but one occurrence of that character.
- Insert the character’s count after it in the list.
- Repeat this process.
Let’s see how the whole process will work:
Let’s look at the code for this solution:
import scala.collection.mutable.ArrayBufferobject Solution {def compress(chars: ArrayBuffer[Char]): ArrayBuffer[Char] = {var i = 0while ( {i < chars.size}) {var count = 1val ch = chars(i)var c = {i += 1; i}// Count the number of times a character repeatswhile ( {i < chars.size && (chars(i) == ch)}) {chars.remove(i)count += 1}if (count > 1) { // Insert the countfor (item <- String.valueOf(count).toCharArray) {c += 1;chars.insert(c-1, item)}i = c}}chars}def main(args: Array[String]): Unit = {val chars = new ArrayBuffer[Char]val input = Array('a', 'a', '2', '2', 'b', 'b', 'b', 'c', 'a', 'a', 'a', 'a')for (ch <- input) {chars.addOne(ch)}val result = compress(chars)for (ch <- result) {print(ch)}}}
Complexity measures
Time complexity | Space complexity |
---|