JavaScript algo: decompress a compressed string-CodePudding

I wanted to write a function that takes a compressed string and outs the decompressed string.

A compressed string like a2b2c3 and the decompress string is aabbccc More examples would be

`a` -> `a`
`ab12` -> `abbbbbbbbbbbb`
`a3b2a2` -> `aaabbaa

I tried to implement it but it is really messy and buggy for compressed strings like ab12

function isNumeric(num) {
    if (num === '') return false
    if (num === null) return false
    return !isNaN(num)
  }
  

function decompress(compressedStr) {
    const array = compressedStr.split('')
    let prevChar, str = ''
    for(let i = 0; i < array.length; i  ) {
        if(i === 0) {prevChar = array[i]}
        if(isNumeric(array[i])) {
            str  = prevChar.repeat(Number(array[i]))
            prevChar = null
        } else {
            if(!prevChar) prevChar = array[i] 
            else {
                str  = prevChar
                prevChar = array[i] 
            }
        }
    }

    return str
}

Now it works for a3b2a2 but it is buggy for cases like ab12 . Need help to rewrite this function to make it work.

CodePudding user response：

You can use String#replace while capturing both the character and the number of times it is to be repeated.

function decompress(str) {
  return str.replace(/(\D)(\d )/g, (_, g1, g2) => g1.repeat(g2));
}
console.log(decompress('a'));
console.log(decompress('ab12'));
console.log(decompress('a3b2a2'));

CodePudding user response：

const is_digit = (ch) => '0' <= ch && ch <= '9'

function decompress(str) {
  if( str.length === 0 ) return ''

  if( is_digit(str[0]) ) return 'invalid input'

  const output = []
  let i = 0
  while(i !== str.length) {

    // collect non-digits into the `output`, stop at the end or at a digit
    while( is_digit(str[i]) === false ) {
      if( i === str.length ) return output.join('')
      output.push(str[i])
        i
    }

    if( i === str.length ) break

    // remember the `ch` with a span
    let ch = str[i-1]

    // parse the span
    let span = 0
    while( is_digit(str[i]) ) {
      if( i === str.length ) break
      span = span * 10   Number(str[i])
        i
    }

    if( span === 0 ) {
      // don't forget about edge cases
      output.pop()
    } else {
      // span-1 because the first `ch` is already in the `output`
      for( let j = 0 ; j !== span-1 ;   j ) {
        output.push(ch)
      }
    }
  }

  return output.join('')
}

// tests
[
  '',
  '12',   // edge case
  'a',
  'ab',
  'a0',   // another edge case
  'ab0',
  'a0b0',
  'a0b',
  'a1',   // yet another
  'a01',  // and another
  'ab1',
  'a1b1',
  'ab01',
  'ab12', // your favorite
  'a12b',
  'a3b2a2',
].forEach((test_case) => console.log('res:', decompress(test_case)))

This is not necessary an optimal solution in JS (there're a lot of magic in V8), so it needs to be tested. But it doesn't looks like the OP is writing a production code, but rather an exercise. So the main points here are

the code always goes forward, so it has an O(N) complexity in speed and memory
it doesn't use string concatenations (because under the hood... well you can not be sure, but you can assume that V8 creates new strings with each concatenation, and it can ruin the complexity)
it doesn't use Number.parseInt or something similar - because, again, that would require new strings to be created

CodePudding user response：

Without regular expressions, you can directly loop through the characters until a non-digit character is reached, then consume all the digit characters after it.

function decompress(str) {
  let prevCh = '', num = '', res = '';
  function append() {
    if (prevCh)
      if (num) res  = prevCh.repeat(num), num = '';
      else res  = prevCh;
  }
  for (const ch of str) {
    if (isNaN(ch)) {
      append();
      prevCh = ch;
    } else num  = ch;
  }
  append();
  return res;
}
console.log(decompress('a'));
console.log(decompress('ab12'));
console.log(decompress('a3b2a2'));