改进运行-length-encoding 算法

Question

我有关于运行-length-encoding 的字符串面试问题，我的解决方案是 O(n)。有什么办法可以改善吗：

输入是 AABBBCAAEE
输出假设为 A2B3C1A2E2

const firstString=(str)=>{
  const arr = str.split('');
  let counter = 1;
  let result ='';
  for (let i=0; i<arr.length; i++){
    if(arr[i] === arr[i+1]){
      counter++;
    } else {
      result +=arr[i]+counter;
      counter = 1;
    }
  } return result
};
firstString('AABBBCAAEE');

Answer 1

改善这一点的一种方法是不执行拆分。字符串也是可索引的：

let firstString = (str) => {
  if (str.length <= 0) {
    return "";
  }
  const result = [];
  result.push(str[0]);
  let counter = 1;
  for (let i = 1; i < str.length; i++) {
    if (result[result.length - 1] === str[i]) {
      counter++;
    } else {
      result.push(counter, str[i]);
      counter = 1;
    }
  }
  result.push(counter);
  return result.join("");
};

Answer 2

将此方法与正则表达式结合使用： Regex to match/group repeating characters in a string

正则表达式解释： /((.)*)/g

var str = 'AABBBCAAEE';
var result = str.replace(/((.)*)/g, function(match) {
  var [letter] = match;
  return `${letter}${match.length}`;
});

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 3

你想要达到的是run-length encoding。

这个问题existing Javascript implementations有不少

Answer 4

Python实施时间 - O(n), Space - O(n)

def encode(_str):
    n = len(_str)

    if _str == _str[0] * n:
        return f'{n}{_str[0]}'

    i, _count = 1, 1
    encoding = ''

    while i < n:
        if _str[i] == _str[i-1]:
            _count += 1
        else:
            encoding += f'{_count}{_str[i-1]}'
            _count = 1

        i += 1

    encoding += f'{_count}{_str[i-1]}'  # last iteration

    return encoding


assert encode('WWWWWW') == '6W'
assert encode('WWWWWWWWWBBBBBBB') == '9W7B'
assert encode('WWWWWWWWWBBBBBBBR') == '9W7B1R'
assert encode('W') == '1W'

改进运行-length-encoding 算法

improve run-length-encoding algorithm

javascript

string

algorithm

encoding

run-length-encoding

改进 运行-length-encoding 算法

improve run-length-encoding algorithm

javascript

string

algorithm

encoding

run-length-encoding

改进运行-length-encoding 算法