c++ - Count space required for RLE-compressed string -


i'm working on interview workbook , doing problem: implement function compress string using counts of repeated characters (aabcccccaaa become a2blc5a3). return original string if "compressed" not smaller original.

a solution found counts size of compressed string before else. i've tried tracing through helper function don't understand logic of line. any deciphering great!:

size = size + 1 + std::to_string(count).length();

count int number of repeated characters in c++11, to_string lets append append ints strings. so, a+1 a1.

better solution:

int countcompression(const string& str) {     if (str.length() == 0)         return 0;      char prev = str[0];     int size = 0;     int count = 1;      (int = 1; < str.size(); i++)     {         // repeated char         if (str[i] == prev)             count++;         // unique char         else         {             prev = str[i];             size = size + 1 + std::to_string(count).length();             count = 1;         }         //cout << "the size in iteration " << << " " << size << endl;     }     size = size + 1 + std::to_string(count).length();     //cout << "the final size is: " << size << endl;     return size; } 

btw, wrote solution, checks size afterwards. wastes space think:

#include <iostream> #include <string>  std::string compress(const std::string &str) {     std::string comp;     char prev = str[0];     int count = 1;     (int = 1; < str.size(); i++)     {         if (prev == str[i])             count++;         else         {             comp += prev;             comp += std::to_string(count);             prev = str[i];             count = 1;         }     }     comp += prev;     comp += std::to_string(count);     if (comp.size() > str.size())         return comp;     else         return str; } 

size = size + 1 + std::to_string(count).length();

this line incrementing size 1 repeated character (a, b, c, etc) plus length() of string representation of numeric count specifies how many times character repeated.

thus:

for aa, 2 added size:

size = size + 1 + to_string(2).length() 

for b, 2 added size:

size = size + 1 + to_string(1).length() 

for ccccc, 2 added size:

size = size + 1 + to_string(5).length() 

for aaa, 2 added size:

size = size + 1 + to_string(3).length() 

so final compressed size 8.

with said, try implementation:

std::string compress(const std::string& str) {     std::string::size_type len = str.length();     if (len > 1) // compressed size 2 chars minimum     {         std::ostringstring compressed;          char ch, prev = str[i];         int count = 1;          (int = 1; < len; ++i)         {             ch = str[i];             if (ch == prev) {                 // repeated char                 ++count;             }             else {                 // unique char                 compressed << prev << count;                 prev = ch;                 count = 1;             }         }          // output final pending char count         compressed << prev << count;          std::string result = compressed.str();         if (result.length() < len)             return result;     }      return str; } 

alernatively:

std::string::size_type compresssize(const std::string& str) {     std::string::size_type len = str.length();     if (len > 1) // compressed size 2 chars minimum     {         std::string::size_type size = 0;          char ch, prev = str[i];         int count = 1;          (int = 1; < len; ++i)         {             ch = str[i];             if (ch == prev) {                 // repeated char                 ++count;             }             else {                 // unique char                 size += (1 + std::to_string(count).length());                 prev = ch;                 count = 1;             }         }          // output final pending char count         size += (1 + std::to_string(count).length());          if (size < len)             return size;     }      return len; }  std::string compress(const std::string& str) {     std::string::size_type len = str.length();      if (compresssize(str) >= len)         return str;      std::ostringstring compressed;     char ch, prev = str[i];     int count = 1;      (int = 1; < len; ++i)     {         ch = str[i];         if (ch == prev) {             // repeated char             ++count;         }         else {             // unique char             compressed << prev << count;             prev = ch;             count = 1;         }     }      // output final pending char count     compressed << prev << count;      return compressed.str(); } 

alternatively:

bool cancompress(const std::string& str) {     std::string::size_type len = str.length();     if (len <= 1) // compressed size 2 chars minimum         return false;      std::string::size_type size = 0;      char ch, prev = str[i];     int count = 1;      (int = 1; < len; ++i)     {         ch = str[i];         if (ch == prev) {             // repeated char             ++count;         }         else {             // unique char             size += (1 + std::to_string(count).length());             if (size >= len) {                 return false;             }             prev = ch;             count = 1;         }     }      // output final pending char count     size += (1 + std::to_string(count).length());      return (size < len); }  std::string compress(const std::string& str) {     if (!cancompress(str))         return str;      std::ostringstring compressed;      char ch, prev = str[i];     int count = 1;      std::string::size_type len = str.length();     (int = 1; < len; ++i)     {         ch = str[i];         if (ch == prev) {             // repeated char             ++count;         }         else {             // unique char             compressed << prev << count;             prev = ch;             count = 1;         }     }      // output final pending char count     compressed << prev << count;      return compressed.str(); } 

Comments

Popular posts from this blog

java - UnknownEntityTypeException: Unable to locate persister (Hibernate 5.0) -

python - ValueError: empty vocabulary; perhaps the documents only contain stop words -

ubuntu - collect2: fatal error: ld terminated with signal 9 [Killed] -