首页 > 试题广场 >

基本字符串压缩

[编程题]基本字符串压缩
  • 热度指数：73053 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

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

示例1

输入

"aabcccccaaa"

输出

"a2b1c5a3"
示例2

输入

"welcometonowcoderrrrr"

输出

"welcometonowcoderrrrr"

说明

welcometonowcoderrrrr转换成重复字母压缩的结果是w1e1l1c1o1m1e1t1o1n1o1w1c1o1d1e1r5，比原字符串的长度还要长，所以返回原先的字符串。
算法知识视频讲解
添加回答
推荐
Ron头像 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)
Billionaire。头像 Billionaire。 
class Zipper {
public:
    string zipString(string iniString) {
	string str;
	int i = 0,j = 0;
	while (i < iniString.length()){
		while (iniString[i] == iniString[j]) i++;
		str += iniString[j];
	        str += to_string(i-j);
		j = i;}
	if (iniString.length() < str.length()) return iniString;
	else return str;
    }
};

发表于 2015-09-17 18:16:15 回复(10)
Java
小风筝0010头像 小风筝0010 
import java.util.*;
//while (i < iniString.length()-1 && iniString.charAt(i+1) == iniString.charAt(i))中的代码是关键
//大家很多遇到的字符串越界关键在此。iniString.charAt(i+1) == iniString.charAt(i)与i < iniString.length()-1 顺序反过来就错了

public class Zipper {
    public String zipString(String iniString) {
          StringBuffer stringBuffer = new StringBuffer();
        for (int i = 0; i < iniString.length(); i++) {
            char temp = iniString.charAt(i);
            int count = 1;
            while (i < iniString.length()-1 && iniString.charAt(i+1) == iniString.charAt(i)) {
                count ++;
                i ++;
            }
            stringBuffer.append(temp).append(count);
        }
        return iniString.length() > stringBuffer.length() ? stringBuffer.toString() :iniString;
    }
}

编辑于 2017-03-14 21:12:17 回复(4)
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)
Java
上海科比头像 上海科比 
//引入一个计数器k就可以了
public class Zipper {
    public String zipString(String iniString) {
       StringBuffer sb = new StringBuffer();
       int k = 1;
       for(int i = 0; i < iniString.length() - 1; i++){
           if(iniString.charAt(i) == iniString.charAt(i+1))
               k++;
           else {
               sb.append(iniString.charAt(i));
               sb.append(k);
               k = 1;
           }
           
       }
        sb.append(iniString.charAt(iniString.length() - 1));
        sb.append(k);
        if(sb.length() >= iniString.length())
            return iniString;
       return sb.toString();
    }
}

编辑于 2017-04-24 09:03:28 回复(4)
从前从前有个人爱你很久头像 从前从前有个人爱你很久 
import java.util.*;

public class Zipper {
    public String zipString(String iniString) {
        char[] c = iniString.toCharArray();
        String str2 = "";
        
        for(int i=0; i<c.length-1; i++){
        	int count = 1;
        	int index = i;
        	for(int j=i+1; j<c.length; j++){
        		if(c[j] == c[i]){
        			count ++;
        			index = j;				//标记与位置i处的字符一样的最后下标
        		}else{
        			break;
        		}
        	}
        	str2 += c[i] + "" + count;		//+"" : 变为字符串
        	i = index;					//i直接跳至最后下标处,因为下个循坏前i++,所以i的实际跳转位置是index+1
        }
        return str2.length() < iniString.length() ? str2 : iniString;
    }
}

发表于 2016-07-07 20:29:57 回复(2)
datong头像 datong 
class Zipper {
public:
    string zipString(string iniString) {
        string s ;
        int cnt = 0;
        for(int i = 0; i < iniString.length(); ++i){
            cnt = 1;
           while(i + 1 < iniString.length() && iniString[i] == iniString[i+1]) {
               cnt ++;
               i++;
           }
                s += iniString[i];
				s += to_string(cnt);
        }
        if(iniString.size() > s.size()) return s;
        return iniString;
    }

};

注意to_string()是c++11之后才添加到string中的，在自己的g++中编译时要加上-std=c++11
发表于 2015-09-12 10:14:20 回复(1)
doubleGanse头像 doubleGanse
 public String zipString(String iniString) {
      StringBuffer sb = new StringBuffer();
        char[] chs = iniString.toCharArray();
        int count = 1;
        for (int i = 1; i < chs.length; i++) {
            if (chs[i - 1] == chs[i]) {
                count++;
            }else{
                sb.append("" + chs[i - 1] + count);
                count = 1;
            }
            if(i==chs.length-1){
                sb.append("" + chs[i - 1] + count);
            }
        }
        return sb.toString().length()<iniString.length()?sb.toString():iniString;
    }

发表于 2015-08-29 16:02:34 回复(0)
Java
lmz9509头像 lmz9509 
import java.util.*;
/**
标签
*/
/*//这种只适合前面出现后面不出现的字符串
public class Zipper {
    public String zipString(String iniString) {
        // write code here
        if(iniString.length()<=2)return iniString;
        StringBuffer sb = new StringBuffer();
        int sIndex = 0;
        int n = iniString.length();
        while(sIndex < n){
            char ch = iniString.charAt(sIndex);
            int eIndex = iniString.lastIndexOf(ch);
            if(sIndex==eIndex){
                sb.append(ch);
                sIndex++;
            }else{
                sb.append(ch);
                sb.append(eIndex-sIndex + 1);
                sIndex = eIndex+1;
            }
        }
        if(n<=sb.length())
            return iniString;
        else
            return sb.toString();
    }
}*/

public class Zipper {
    public String zipString(String iniString) {
        // write code here
        if(iniString.length()<=2)return iniString;
        StringBuffer sb = new StringBuffer();
        int sIndex = 0;
        int n = iniString.length();
        while(sIndex < n){
            char ch = iniString.charAt(sIndex);
            int temp = 0;
            while(sIndex < n && ch==iniString.charAt(sIndex)){
                temp++;
                sIndex++;
            }
            sb.append(ch);
            sb.append(temp);
        }
        if(n<=sb.length())
            return iniString;
        else
            return sb.toString();
    }
}

编辑于 2020-06-12 19:22:38 回复(0)
Copyright头像 Copyright 
class Zipper {
public:
    string zipString(string iniString) {
        long    int num=0,i=0,k=1;
        string temp;
        num=iniString.size();
        for ( i = 1; i < num; i++)
        {
            if (iniString[i] != iniString[i-1])
            {
                temp += iniString[i-1] ;
                if(k>9)
                {
                    temp += to_string(k);
                }
                else
                {
                    temp += k+'0';
                }
                k=1;
            }
            else if (iniString[i] == iniString[i-1])
            {
                k++;
            }
            if (i== num-1)
            {
                temp += iniString[i];
                if(k>9)
                {
                    temp += to_string(k);
                }
                else
                {
                    temp += k+'0';
                }
            }
        }
        if (temp.size()<=iniString.size())
        {
            return temp;
        }
        return iniString;
    }
};

发表于 2020-02-04 15:25:48 回复(0)
Butterfliesflyaway↘头像 Butterfliesflyaway↘ 
public class Zipper {
    public String zipString(String iniString) {
        StringBuffer res = new StringBuffer();
        StringBuffer tmp = new StringBuffer(); //用来存放一组相同的字符
        
        tmp.append(iniString.charAt(0));
        for(int i=1; i<iniString.length(); i++) {
            //如果当前字符与前一个字符相同，则存入tmp中
            if(iniString.charAt(i) == iniString.charAt(i-1)) {
                tmp.append(iniString.charAt(i));
            }else { //如果当前字符与前一个字符不相同，将tmp中的首字符以及tmp长度加入res中
                res.append(tmp.charAt(0));
                res.append(tmp.length());
                tmp.setLength(0);
                tmp.append(iniString.charAt(i));
            }
        }
        if(tmp.length() != 0) { //将最后一组tmp字符值存入res中
            res.append(tmp.charAt(0));
            res.append(tmp.length());
        }
        //如果压缩后的长度变小，则返回压缩后的字符串，否则返回原字符串
        if(res.length() < iniString.length()) return res.toString();
        return iniString;
    }
}

发表于 2019-04-03 10:08:23 回复(0)
。。。。。。20190227205038头像 。。。。。。20190227205038
class Zipper {
public:
    string zipString(string iniString) {
        string c="";
        int n=1,j,i=0;
        while(iniString[i]!='\0')
        {
        for( j=i+1;iniString[j]!='\0';j++)
        {
            if(iniString[i]==iniString[j])n++;
            else break;
          }
            c+=iniString[i];
            c+=to_string(n);
            i=j;
            n=1;
        }
        if(iniString.size()>c.size()) return c;
        else return iniString;
    }
};

发表于 2019-03-03 23:07:58 回复(0)
木然猫猫头像 木然猫猫
很平凡的思路。pre记录上个字符，cnt为当前字符计数，ss存储压缩串，只要记得循环完再加一下压缩串就行了。 
# -*- coding:utf-8 -*-
class Zipper:
    def zipString(self, iniString):
        pre = ''
        cnt = 0
        ss = ''
        for s in iniString:
            if s == pre:
                cnt += 1
            else:
                if pre:
                    ss += pre + str(cnt)
                pre = s
                cnt = 1
        ss += pre + str(cnt)
        if len(ss) < len(iniString):
            return ss
        else:
            return iniString

运行时间：60ms

占用内存：5852k


发表于 2018-09-26 15:21:48 回复(0)
Java
小先生201804151329945头像 小先生201804151329945 
public class Zipper {
    public static String zipString(String iniString) {
        String temp1=iniString+";";
        StringBuffer temp2=new StringBuffer();
        int count=1;
        for(int i=1;i<temp1.length();i++) {
           if(temp1.charAt(i)==temp1.charAt(i-1)&& i<temp1.length()-1) {
               count++;
           }else{
               temp2.append(iniString.charAt(i-1));
               temp2.append(count);
               count=1;
           }
       } 
        if(temp2.length()>=temp1.length()) {
            return iniString;
        }
            return temp2.toString();
    }
}

编辑于 2018-04-23 15:58:52 回复(0)
大夫都不敢治我头像 大夫都不敢治我 
import java.util.*;
public class Zipper {
    public String zipString(String iniString) {
        int count = 1;
        char a = ' ';
        StringBuffer sb = new StringBuffer();
        for(int i = 1; i < iniString.length(); i++) {
            a = iniString.charAt(i-1);
            if(a == iniString.charAt(i)) {
                count++;
            }else {
                sb.append(a).append(count);
                count = 1;
            }
        }
        if(iniString.length() < sb.length()) return iniString;
        else return sb.append(a).append(count).toString();  
    }
}

发表于 2018-03-27 11:03:23 回复(0)
hopes头像 hopes 
import java.util.*;

public class Zipper {
    public static String zipString(String iniString) {
        // write code here
        StringBuilder result = new StringBuilder();
        int count = 1;
        int i = 1;
        while (i < iniString.length()) {
            if (iniString.charAt(i - 1) == iniString.charAt(i)) {
                count++;
            } else {
                result.append(iniString.charAt(i - 1));
                result.append(count);
                count = 1;
            }
                 //最后一个字符判断不了，重新加载一次
            if (i == iniString.length() - 1) {
                result.append(iniString.charAt(i - 1));
                result.append(count);
            }
            i++;
        }
        if (result.length() > iniString.length()) {
            return iniString;
        }
        return String.valueOf(result);
    }

}

发表于 2017-11-23 17:19:50 回复(0)
Java
在沙雕路上越走越远头像 在沙雕路上越走越远

public class Zipper {
    public String zipString(String iniString) {
        String mystr ="";
        char last = iniString.charAt(0);         //先存放第一个字符，循环最后用于存放最后的字符
        int count =1;       //用来存储相同字符串个数
        for(int i=1;i<iniString.length();i++){        //从字符串第二个开始，进行比较
            if(iniString.charAt(i)==last){          //相同，count+1
              count++;                                
          
            }
            else{
                mystr+=last+""+count;               //不相同，mystr用来放字符和次数
                last=iniString.charAt(i);               //将字符往后移，保存在last中
                count=1;                                      //重新将count置1
            }
        }
        String str = mystr+last+count;           
        if(str.length()>=iniString.length()){      //比较原字符和压缩后的字符长度，压缩后没变短返回原字符
            return iniString;
        }else
        return str;
    }
}
发表于 2017-09-23 18:04:37 回复(0)
~一念执着~头像 ~一念执着~ 
//扫描一遍，边扫描边保存压缩后的字符串，最后比较和原来的长度相比有没有变短，
//决定返回压缩后的字符串或者原串。

class Zipper {
public:
	string zipString(string iniString) {
		int n = iniString.size();
		if (n == 0)
			return iniString;
		string s;
		int i = 0;
		char tmp;
		while (i<n) {
			tmp = iniString[i];
			int cnt1 = 0;
			while (i<n&&tmp == iniString[i]) {
				i++;
				cnt1++;
			}
			s += tmp;
			s += to_string(cnt1);
		}
		return ((s.size()<n) ? s : iniString);
	}
};

编辑于 2017-08-13 15:54:08 回复(0)
NLXJ头像 NLXJ 
import java.util.*;

public class Zipper {
    public String zipString(String iniString) {
     
        StringBuffer sb = new StringBuffer();
        char[] strArr = iniString.toCharArray();
        int index = 1;
        boolean f = true;
        for (int i = 0; i < strArr.length; i++) {
        	
        	char m = strArr[i];
        	char n;
			try {
				n = strArr[i+1];
			} catch (Exception e) {
				sb.append(m+""+(index));
				if(f){
		        	return iniString;
		        }else{
		        	return sb.toString();
		        }
			}
        	if(m!=n){
        		sb.append(m+""+(index));
        		index=1;
        	}else{
        		f = false;
        		index++;
        	}
		}
        if(f){
        	return iniString;
        }else{
        	return sb.toString();
        }
       
       
    }
       
}

发表于 2017-07-20 14:32:08 回复(0)
Python
恭喜你又收割一个offer！头像 恭喜你又收割一个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)
C/C++
梦泽头像 梦泽
class Zipper {
public:
    string zipString(string iniString) {
        // write code here
string str;
        int len =  iniString.size();
int j=0;
while (iniString[j] != '\0'){
char ch = iniString[j];
int i=j+1;
while ((ch == iniString[i]) && (i<=len)){
i++;
} 
str.push_back (ch);
char ch1 = i-j;
str = str + to_string(i-j);
j=i;
}
int len_str=str.size();
if (len_str<len) 
return str;
else 
return iniString;
    }
};
发表于 2017-06-27 16:37:14 回复(0)
提交观点

问题信息

字符串
难度：
339条回答 53810浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号