首页 > 试题广场 >

基本字符串压缩

[编程题]基本字符串压缩

热度指数：73175 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

现给定一个string iniString字符串(长度小于等于10000)，请按连续重复字母压缩的方式将该字符串压缩，返回结果为string，比如，字符串“aabbcccccaaa”经压缩会变成“a2b2c5a3”，若压缩后的字符串没有变短，则返回原先的字符串。注意保证串内字符均由大小写英文字母组成。

示例1

输入

"aabcccccaaa"

输出

"a2b1c5a3"

示例2

输入

"welcometonowcoderrrrr"

输出

"welcometonowcoderrrrr"

说明

welcometonowcoderrrrr转换成重复字母压缩的结果是w1e1l1c1o1m1e1t1o1n1o1w1c1o1d1e1r5，比原字符串的长度还要长，所以返回原先的字符串。

算法知识视频讲解

推荐

Ron

import java.util.*;

public class Zipper {
	public String zipString(String iniString) {
		// write code here
		if(iniString==null||iniString.trim().length()==0){
			return "";
		}
		StringBuilder strB = new StringBuilder("");
		char[] iniStr = iniString.toCharArray();
		char pre;
		pre = iniStr[0];
		int count = 1;
		for(int i = 1;i < iniStr.length; i++){
			if(pre == iniStr[i]){
				count++;
			}else{
				strB.append(pre+""+count);
				pre = iniStr[i];
				count = 1;
			}
		}
		strB.append(pre+""+count);
		if(strB.toString().length() >= iniString.length()){
			return iniString;
		}
		return strB.toString();
	}
}

编辑于 2015-10-14 14:31:45 回复(18)

Python

甲壬

思路和其他的都差不多，只是需要先去除输入里面非字符的干扰：

class Zipper:
    def zipString(self, iniString):
        # write code here
        res = ''
        i = 0
        s = iniString.strip('"')
        n = len(s)
        
        while i < n:
            j = i
            while j < n and s[j] == s[i]:
                j += 1
            res += s[i]
            res += str(j-i)
            i = j
        if len(res) < len(s):
            return res
        else:
            return iniString

运行时间：30ms
超过98.70%用Python提交的代码

占用内存：5744KB
超过38.18%用Python提交的代码

发表于 2021-05-16 08:17:45 回复(0)

Python

百年da孤独

 def zipString(self, iniString):
        # write code here
        from collections import deque
        pre = iniString[0]
        d = deque()
        d.append(pre)
        cnt = 1
        for x in iniString[1:]:
            if x == pre:
                cnt+=1
            else:
                d.append(str(cnt))
                d.append(x)
                cnt = 1
                pre = x
        else:
            d.append(str(cnt))
        return iniString if len("".join(d)) >= len(iniString) else "".join(d)

发表于 2018-12-18 12:26:27 回复(0)

Python

正在卷的马里奥

class Zipper:
    def zipString(self, iniString):
        # write code here
        num = 1
        res_str = ''
        for i in range(len(iniString)):
            try:
                if iniString[i] == iniString[i+1]:
                    num += 1
                else:
                    res_str += (iniString[i] + str(num))
                    num = 1
            except:
                if iniString[i] == iniString[i-1]:
                    res_str += (iniString[i] + str(num))
                else:
                    res_str += (iniString[i] + '1')
        if len(res_str) >= len(iniString):
            return iniString
        else:
            return res_str

新建一个字符串保存压缩后的串

发表于 2018-08-22 16:49:37 回复(0)

Python

灵外＆棂外

# -*- coding:utf-8 -*-
class Zipper:
def zipString(self, iniString):
# write code here
s,t=iniString[0],1
for i in range(1,len(iniString)):
if iniString[i]==iniString[i-1]:
t=t+1
else:
s,t=s+str(t)+iniString[i],1
s+=str(t)
return s if len(s)<len(iniString) else iniString

发表于 2018-06-01 16:59:46 回复(0)

Python

华科平凡

python solution

主要思路：使用一个中间变量strCnt表示字符的数量，如果下一个字符与当前的字符不相等，把strCnt置为1即可。遍历完字符串，结果出就出来了。

class Zipper:
    def zipString(self, iniString):
        zipStr = ""
        strCnt = 1
        for i in range(len(iniString) - 1):
            if iniString[i + 1] == iniString[i]:
                strCnt += 1
            else:
                zipStr += iniString[i] + str(strCnt)
                strCnt = 1
        zipStr += iniString[-1] + str(strCnt)
        return zipStr if len(zipStr) < len(iniString) else iniString

编辑于 2017-10-03 17:29:41 回复(1)

Python

恭喜你又收割一个offer！

两个列表，一个用来输出原始字符串，一个用来输出改变后的字符串; 属于暴力破解:

# -*- coding:utf-8 -*-
class Zipper:
    def zipString(self, iniString):
        # write code here
        iniString = list(iniString)
        resultlst1 = []
        resultlst2 = []
        count = 0
        lens = len(iniString)
        i = 0
        
        while i < lens:
            j = i + 1
            resultlst1.append(iniString[i])
            count += 1
            while j < lens and iniString[i] == iniString[j]:
                count += 1
                j += 1
            else:
                resultlst1.append(str(count))
                resultlst2.append(str(count))
                i = j
                count = 0
        
        
        if len(resultlst2) == lens:
            return ''.join(iniString)
            
        return ''.join(resultlst1)

发表于 2017-06-29 21:25:15 回复(0)

Python

jay3zhang

def zipString(self, iniString):
        # write code here
        zipstr = ''
        same = 1
        for i in range(0,len(iniString)-1):
            if iniString[i]==iniString[i+1]:
                same +=1
            else:     #与后一位比较，相同same+1，不同same置为1
                zipstr = zipstr+iniString[i]+str(same)
                same = 1 

        zipstr = zipstr+iniString[i]+str(same)

        if len(zipstr)>len(iniString):
            return iniString
        else:
            return zipstr

编辑于 2017-06-06 16:08:29 回复(0)

Python

啥也没有

class Zipper:
    def zipString(self,iniString):
    # write code here
            if not iniString:
                return
            i = 0
            res = ''
            while i != len(iniString):
                if i == len(iniString) - 1:
                    res += iniString[-1] + '1'
                    i += 1
                    continue
                if iniString[i] != iniString[i + 1]:
                    res += iniString[i] + '1'
                    i += 1
                    continue
                else:
                    size = 3
                    while len(set(iniString[i:(i + size)])) == 1:
                        if i+size-1 == len(iniString):
                            break
                        size += 1
                    res += iniString[i] + str(size - 1)
                    i = i + size - 1
                    continue
            if len(res) < len(iniString):
                return res
            else:
                return iniString

发表于 2017-05-06 15:46:35 回复(0)

Python

0x100000001b3

# -*- coding:utf-8 -*-
class Zipper:
    def zipString(self, iniString):
        # write code here
        L = len(iniString)
        current = iniString[0]
        times = 1
        result = ''
        for i in xrange(1, L):
            if iniString[i] == current:
                times += 1
            else:
                result += iniString[i - 1] + str(times)
                times = 1
                current = iniString[i]
        result += current + str(times)
        if len(iniString) <= len(result):
            return iniString
        else:
            return result

发表于 2016-12-27 21:59:55 回复(0)

Python

你跺你也麻

用python的人少啊，我来支持一下，相比下python代码量少点吧

# -*- coding:utf-8 -*-
class Zipper:
    def zipString(self, iniString):
        # write code here
       	k=0
        s=""
        while k<len(iniString):
            tempNum=1 #字符重复个数计数
            for i in range(k,len(iniString)):
                if i<(len(iniString)-1) and iniString[i]==iniString[i+1]:
                    tempNum+=1
                else:
                    s+=(iniString[i]+str(tempNum))
                    break 
            k+=tempNum
       	if len(s)<len(iniString):
            return s
        else:
            return iniString

编辑于 2016-09-19 19:26:33 回复(1)

提交观点

问题信息

字符串

难度：

10条回答 318收藏 57607浏览

通过挑战的用户

查看代码

牛客45135...

2023-01-06 22:37:20
牛客66527...

2022-10-13 19:55:31
牛客79984...

2022-09-30 07:09:39
rainbow...

2022-09-17 21:27:42
柒月安余生

2022-09-07 23:02:00

基本字符串压缩

输入

输出

输入

输出

说明

python solution

问题信息

热门推荐

通过挑战的用户

相关试题