题解 | #小红的字符串构造#
小红的字符串构造
https://www.nowcoder.com/practice/3e4b4dabc2e444e384c3ae62ac7dd84e
解题思路
这是一个字符串构造问题，要求构造的新字符串t在每个位置上都和原字符串s不同，但使用的字符集必须相同。
解题思路如下：
- 首先获取原字符串s的字符集（去重后的所有字符）
- 如果字符集大小为1，则无法构造（因为每个位置都必须不同）
- 对于字符集大小≥2的情况，把当前字符变为字符集内位置的下一位
代码
#include <iostream>
#include <string>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(0);
string s;
cin>>s;
set<char> chk(s.begin(),s.end());
vector<char> v(chk.begin(),chk.end());
int m=v.size(),w;
if(m==1)
{
cout<<"-1";
return 0;
}
for(char &c:s)
{
w=find(v.begin(),v.end(),c)-v.begin();
cout<<v[(w+1)%m];
}
return 0;
}
import java.util.*;
public class ZT6 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s=sc.next();
int n=s.length(),m,i,w;
Set<Character> chk=new HashSet();
for(i=0;i<n;++i)
chk.add(s.charAt(i));
ArrayList<Character> v=new ArrayList(chk);
m=v.size();
if(m==1)
System.out.println(-1);
else{
for(i=0;i<n;++i){
w=v.indexOf(s.charAt(i));
System.out.print(v.get((w+1)%m));
}
}
}
}
s=input()
v=list(set(s))
m=len(v)
if(m==1):
print(-1)
else:
for i in s:
w=v.index(i)
print(v[(w+1)%m],end='')
算法及复杂度
- 算法：构造法。使用字符集中的字符交替构造新字符串。
- 时间复杂度：
，其中n为字符串长度。
- 空间复杂度：
，其中k为字符集大小，一般不超过26。
