首页 > 试题广场 > 字符串替换
[编程题]字符串替换
  • 热度指数:20641 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

请你实现一个简单的字符串替换函数。原串中需要替换的占位符为"%s",请按照参数列表的顺序一一替换占位符。若参数列表的字符数大于占位符个数。则将剩下的参数字符添加到字符串的结尾。

给定一个字符串A,同时给定它的长度n及参数字符数组arg,请返回替换后的字符串。保证参数个数大于等于占位符个数。保证原串由大小写英文字母组成,同时长度小于等于500。

测试样例:
"A%sC%sE",7,['B','D','F']
返回:"ABCDEF"

python3行解法如下:

class StringFormat:
    def formatString(self, A, n, arg, m):
        while "%s" in A and len(arg)>0:
            A=A.replace("%s",arg.pop(0),1)
        return A+"".join(arg)
发表于 2017-09-12 14:00:20 回复(2)
我所想到的三种方法如下:
第一种方法的思路是 通过字符串的indexOf 方法和replaceFirst方法 进行替换字符串中的%s,然后进行判断参数args里面的参数是否使用完毕,如果没有使用完毕则进行追加到字符最后。 这种方法的缺点是会在内存中生成很多的冗余字符串。优点是 像我这种菜鸟很容易想到,也更与理解。
public String formatString(String A, int n, char[] arg, int m) {       
         int i = 0;
		while (A.indexOf("%s") >= 0) {
			A = A.replaceFirst("%s", String.valueOf(arg[i]));
			i++;
		}
		while (i < m) {
			A += arg[i];
			i++;
		}
		return A;
}
第二种方法的思路通过字符串分割split 方法,把字符串中不是%s的分割出来,存储到数组中,然后遍历这个数组,进行追加参数,但是有一点需要注意字符的开始字符为%s,这样再数组的第一个位置为空串,进行特殊判断即可。这种方法的有点是有效的利用了内存,减少了很多冗余的字符生成。
public String formatString(String A, int n, char[] arg, int m) {
		// write code here
		String[] AArr = A.split("%s");
		StringBuffer buffer = new StringBuffer();
		int i = 0;
		for (String str : AArr) {
			if (str.length() == 0) {
				buffer.append(arg[i]);
			} else {
				buffer.append(str + arg[i]);
			}
			i++;
		}
		while (i < m) {
			buffer.append(arg[i]);
			i++;
		}
		return buffer.toString();
	}
第三种就是通过和正则表达式进行组合,通过matcher添加到buffer里面,进行替换%s,最后需要注意把最尾部的字符添加到buffer里面。
public String formatString(String A, int n, char[] arg, int
      m) {
        // write code here
      Pattern pattern = Pattern.compile("%s");
Matcher matcher = pattern.matcher(A);
StringBuffer buffer = new StringBuffer();
int i = 0;
boolean result = matcher.find();
while (result) {
matcher.appendReplacement(buffer,
      String.valueOf(arg[i]));
result=matcher.find();
i++;
}
matcher.appendTail(buffer);
while (i < m) {
buffer.append(arg[i]);
i++;
}
return buffer.toString();
    }

编辑于 2015-10-09 09:33:27 回复(8)
萌头像
string formatString(string A, int n, vector<char> arg, int m) 
	{
		// write code here
		int pos = A.find_first_of("%s");
		int i = 0;
		while (pos!=string::npos)
		{
			A.replace(pos, 2, 1, arg[i++]);
			pos = A.find_first_of("%s");
		}
		while (i<m)
		{
			A.push_back(arg[i++]);
		}
		return A;
	}
编辑于 2016-05-04 13:36:43 回复(0)
// 该问题可以在O(n)时间内处理完毕,如下。
string formatString(string A, int n, vector<char> arg, int m) {
        // write code here
        int i = 0, j = 0, k = 0;
        while(i < n){
            if(A[i] == '%' && i + 1 < n && A[i + 1] == 's'){
                A[j++] = arg[k++];
                i += 2;
            }else{
                A[j++] = A[i++];
            }
        }
        
        while (k < m){
			if (j < n)
				A[j++] = arg[k++];
			else
				A.push_back(arg[k++]);
		}
		if (j < n)
			A[j] = '\0';
		return A;   
    }

发表于 2016-12-22 15:14:40 回复(1)
//题目比较简单,常规做法可能就是替换操作,但是用一个字符替换两个字符,造成的代价就是
    //替换完成之后后面的字符全部要向前移动一位。
    //所以对于长度为n的字符串来说时间复杂度为O(n2);
    //其实可以优化到O(n)的时间复杂度,那就是用两个指针
    //第一个指针指向给定的字符串,然后依次遍历
    //第二个指针指向一个新的字符串,如果第一个指针检测到%s那么就在新的字符串里面复制arg里面的值
    //否则的话就复制给定的字符串的值。思路很简单,具体代码如下。
    public String formatString(String A, int n, char[] arg, int m) {
        StringBuffer sb = new StringBuffer();
        int j = 0 ;
        for(int i = 0 ; i< n ; i++){
            if(A.charAt(i)=='%'){
                sb.append(String.valueOf(arg[j]));
                j++;
            }else if(A.charAt(i)=='s'){
                sb.append("");
            }else{
                sb.append(String.valueOf(A.charAt(i)));
            }
        }
        while(j<m){
           sb.append(String.valueOf(arg[j])) ;
           j++;
        }
        return sb.toString();
    }

发表于 2016-08-25 11:20:17 回复(0)
       需要注意的是%s在字符串里面是两个字符%和s,而参数列表的字符数是用一个字符去替换%s,因此比较好的办法是用一个新的字符串h来存取目的字符串。
       首先遍历整个给定的参数数组A,如果当前字符A[i]=='%'&&A[i+1]='s',则将参数列表的第一个字符存取到h中(注意此时i应该加1,因为是用一个参数列表字符代替了两个字符%s),否则将A[i]本身的字符存到h中,最后还需要判断   参数列表的字符是否有多余的。若果有,将其放到h后面。代码如下:
class StringFormat {
public:
    string formatString(string A, int n, vector<char> arg, int m) {
        // write code here
        string h;    
        int j=0;
        for(int i=0;i<n;i++)
        {
            if(A[i]=='%'&&A[i+1]=='s')
               {
                  h=h+arg[j]; 
                  i++;
                  j++;
               }
            else
               {
                  h=h+A[i];                
               }
        }
        if(j<m)
        {
            h=h+arg[j];
            j++;
        }
        return h;
    }
};
 
发表于 2017-04-19 10:02:10 回复(4)
class StringFormat {
public:
    string formatString(string A, int n, vector<char> arg, int m) {
        string h;
        int j=0;
        for(int i=0;i<n;i++)
            {
            if(A[i]=='%'&&A[i+1]=='s')
            {h+=arg[j++]; i++;}
            else h+=A[i];
        }
        
        while(j<m)
            h+=arg[j++];

        return h;
        // write code here
    }
};

发表于 2015-10-17 18:52:15 回复(2)
class StringFormat:
    def formatString(self, A, n, arg, m):
        k, d = A.split("%s"), []
        i = 0
        for p in k:
            d.append(p)
            d.append(arg[i])
            i += 1
        d.extend(arg[i:m])
        return ''.join(d)

发表于 2017-06-25 20:32:54 回复(0)
感觉有必要以后处理字符串的题用python去写。。
发表于 2017-11-06 16:41:28 回复(0)
public String formatString(String A, int n, char[] arg, int m) {
            StringBuilder res = new StringBuilder();
            //count对应arg的查询下标
            int count = 0;
            for(int i = 0 ; i<A.length(); i ++){
                //利用Ascll码表对应的数值进行逻辑判断
                if( A.charAt(i) ==37 && A.charAt(i+1) ==115 ){
                    if(count < m){
                        res.append(arg[count++]);
                        //跳过's'字符的遍历,进入下一个字符的匹配
                        i++;
                    }
                }else{
                    res.append(A.charAt(i));
                }
            }
            //遍历完了字符串A后,仍未超过给定的arg字符个数之前,将剩余arg字符加到最后
            while(count<m){
                res.append(arg[count]);
                count++;
            }
            return res.toString();
        }

发表于 2020-03-25 21:36:25 回复(0)
class StringFormat:
    def formatString(self, A, n, arg, m):
        for i in arg:
            if A.find('%s') != -1:
                A = A.replace('%s',i,1)
            else:
                A += i
        return A
编辑于 2018-10-20 00:14:40 回复(0)
import java.util.*;

public class StringFormat {
    public String formatString(String A, int n, char[] arg, int m) {
            String result="";
            int j=0;
            for(int i=0;i<A.length();i++){
                if(A.charAt(i)=='%'){
                    i++;
                    if(j<m){
                        result+=arg[j];
                        j++;
                    }
                }else{
                    result+=A.charAt(i);
                }
            }
            while(j<m){
                result+=arg[j];
                j++;
            }
            return result;
    }
} 

发表于 2018-10-10 20:04:37 回复(0)
class StringFormat {
public:
    string formatString(string A, int n, vector<char> arg, int m) {
        string S = "";
        int j = 0;
        for(int i=0;i<n;i++)
        {
            if(A[i]=='%')
            {
                S += arg[j++];
                i++;              }else{                 S += A[i];             }         }         while(j<m)             S += arg[j++];                      return S;
    }
};

发表于 2017-10-26 11:19:36 回复(0)
//字符串啊,字符串啊,不是他吗的字符数组,日了狗!
class StringFormat {
public:
    string formatString(string A, int n, vector<char> arg, int m) {
        string B;
        int i,j=0,q=0;
        for(i=0;i<n;i++){
            if( A[i] == '%' && A[i+1] == 's'){
                B += arg[q++];
                i++;
            }
            else{
                B += A[i];
            }
        }
        if(q<m)
            B += arg[q++];
        return B;
    }
};

发表于 2017-07-16 21:25:26 回复(2)
NJ头像 NJ
#include <iostream>
#include <vector>
#include <string>
using namespace std;

string EVE(string &a, int n, vector<char> &v1, int m)
{
	if (n == 0)
		return a;
	string Final;
	int i = 0;
	int j = 0;
	for (;i != n;++i)
	{
		if (a[i] == '\0')
			break;
		if (a[i] == '%'&&a[i + 1] == 's')
		{
			Final += v1[j];
			++i;
			++j;
		}
		else
			Final += a[i];
		
	}
	if (j < m)
	{
		for (int c = j ;c != m;++c)
			Final += v1[c];
	}
	for (int i = 0;i != Final.size();++i)
		cout << Final[i] << endl;
	return Final;
}


void main()
{
	string a = "A%sC%sE";
	vector<char> v2 = { 'B','D','M','k' };
	EVE(a, 8, v2, 4);
}
望大神批评指正!

发表于 2017-07-13 20:49:35 回复(0)
//处理字符串,转成StringBuilder
import java.util.*;

public class StringFormat {
    public String formatString(String A, int n, char[] arg, int m) {
        // write code here
        StringBuilder sb =new StringBuilder(A);
        int k=0;
        for(int i=0;i<sb.length()-1;i++){
            if(sb.charAt(i)=='%'&& sb.charAt(i+1)=='s'){
                sb.replace(i,i+2,arg[k++]+""); //String.valueOf()
                
                
            }
        }
        if(k<arg.length){//==时,刚好替换完
            for(int i=k;i<arg.length;i++){
                sb.append(arg[i]);
            }
        }
        return new String(sb);
    }
}

发表于 2017-03-05 12:49:54 回复(1)
import java.util.*;

public class StringFormat {
    public String formatString(String A, int n, char[] arg, int m) 
    {
        // write code here
        StringBuilder sb = new StringBuilder();
        int j=0;
        
        for (int i=0; i<n; i++)
        {
            if (A.charAt(i) == '%')
            {
                sb.append(arg[j++]);
                i++;
            }
            else
                sb.append(A.charAt(i));
        }
        while (j<m)
            sb.append(arg[j++]);
        
        return sb.toString();
    }
}

发表于 2016-12-29 16:39:17 回复(0)
偷了懒,直接用字符串的split()方法,依次往stringbuffer的对象中添加
import java.util.*;

public class StringFormat {
    public String formatString(String A, int n, char[] arg, int m) {
        // write code here
        StringBuilder builder=new StringBuilder();
        
        String[] strArr=A.split("%s");
        
        for(int i=0;i<strArr.length-1;i++)
        {
            
            builder.append(strArr[i]);
            builder.append(arg[i]);            
        }
        builder.append(strArr[strArr.length-1]);
        if(m>=strArr.length)
        {
         for(int i=strArr.length-1;i<m;i++)
                {
                builder.append(arg[i]);                
            }
        }
        
        return builder.toString();

    }
}
发表于 2016-08-28 21:47:44 回复(0)
class StringFormat {
public:
    string formatString(string A, int n, vector<char> arg, int m) {
        // 不调用类函数的方法,先算最后字符串的大小,再逐个填充;避免超出内存限制
        int count = 0;
        for(int i = 0;i<n;i++){
            if(A[i]=='%' && i < n-1 && A[i+1]=='s') count++;
        }
        int newLen = n-count*2+m;
        string ret = string(newLen,'0');
        int index = 0;
        int j = 0;
        for(int i = 0; i<n;i++){
            if(A[i]=='%' && A[i+1]=='s'){
                ret[j++] = arg[index++];
                i++;
            }
            else{
                ret[j++] = A[i];
            }
        }
        while(index<m){
            ret[j++] = arg[index++];
        }
        return ret;
    }
};

编辑于 2016-08-15 17:22:52 回复(0)
class StringFormat {
public:
    string formatString(string A, int n, vector<char> arg, int m) {
        string s;
        int k=0;
        for(int i=0;i<n;i++){
            if(i<n-1&&A[i]=='%'&&A[i+1]=='s'){
                s+=arg[k++];
                i++;
            }else{
                s+=A[i];
            }  
        }
        while(k<m){
            s+=arg[k++];
        }
        return s;
    }
};

发表于 2016-08-15 10:49:34 回复(0)