首页 > 试题广场 >

字符串的排列

[编程题]字符串的排列
  • 热度指数:5050 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。


输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母,例如ac


输出描述:
[ac, ca]
示例1

输入

acc

输出

[acc, cac, cca]
//全排列算法+最后map排序即可
#include<iostream>
(720)#include<cstring>
#include<map>
using namespace std;
map<string,int> mm;
void Array(char *s,int k,int m)
{
    if(k==m)
        mm[s]++;
    else
    {
        for(int j=k;j<=m;j++)
        {
            swap(s[j],s[k]);
            Array(s,k+1,m);
            swap(s[j],s[k]);
        }
    }
}
int main()
{
    char s[10];
    cin>>s;
    Array(s,0,strlen(s)-1);
    auto ot=mm.end();
    ot--;
    for(auto it=mm.begin();it!=mm.end();it++)
    {
        if(it==mm.begin())
            cout<<'['<<it->first<<','<<" ";
        else if(it==ot)
            cout<<it->first<<']';
        else
            cout<<it->first<<','<<" ";
    }
}

发表于 2020-04-13 11:13:46 回复(1)

JavaScript(Node) 😎题目:蘑菇街🍄-字符串全排列无重复(穷举+递归+输出格式(整吐了))

leetcode46、47

const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    ouput: process.stdout
})
let inArr = []
rl.on('line',line=>{
    if(!line) return
    inArr.push(line.trim())
    if(inArr.length === 1){
        let arr = inArr[0].split('')
        let res = permuteUnique(arr).map(e=>e.join(''))
        res.sort()
        let str = ''
        for (let i = 0; i < res.length; i++) {
            if(i==0){
                str += '['+res[i] +', '
            }else if(i==res.length-1){
                str += res[i] +']'
            }else{
                str += res[i]+', '
            }
        }
        console.log(str)
    }
})
var permuteUnique = function(nums) {
    if (nums.length === 0) {
        return [];
    }
    if (nums.length === 1) {
        return [nums];
    }
    
    let [num, ...restNums] = nums;
    let resArr=permuteUnique(restNums).reduce((res, iter) => {
        let iterRes = [];
        for (let i = 0; i <= iter.length; i++) {
            let tmp = [...iter];
            tmp.splice(i, 0, num);
            iterRes.push(tmp);
        }
        return res.concat(iterRes);
    }, []);
    let res={}
        resArr.forEach(item=>{
            res[item]=item;
        });
        return Object.values(res)
};


发表于 2020-02-26 22:29:24 回复(0)
//dfs+set去重
#include <bits/stdc++.h>
using namespace std;
void dfs(int len,string temp,string &str,vector<bool> &vis,set<string> &ans){
    if(len>=str.size()){
        ans.insert(temp);
        return;
    }
    for(int i=0;i<str.size();i++){
        if(vis[i])
            continue;
        vis[i]=true;
        dfs(len+1,temp+str[i],str,vis,ans);
        vis[i]=false;
    }
}
int main(){
    string str;
    set<string> ans;
    vector<bool> vis(str.size(),false);
    cin>>str;
    dfs(0,"",str,vis,ans);
    set<string>::iterator it=ans.begin();
    cout<<"[";
    while(it!=ans.end()){
        cout<<*it;
        if(++it!=ans.end())
            cout<<", ";
    }
    cout<<"]";
    return 0;
}

发表于 2019-11-16 10:53:09 回复(0)
输出格式不对,但结果对~~
importjava.util.Scanner;
importjava.util.HashSet;
 
publicclassMain {
 
    publicstaticvoidprintallPer(String str) {
        char[]chars = str.toCharArray();
        process2(chars,0);
    }
 
    publicstaticvoidprocess2(char[] chs, inti) {
        if(i == chs.length) {
            System.out.print(String.valueOf(chs));
        }
        HashSet<Character> set = newHashSet<>();
        for(intj = i; j < chs.length; j++) {
            if(!set.contains(chs[j])) {
                set.add(chs[j]);
                swap(chs, i, j);
                process2(chs, i + 1);
                //swap(chs, i, j);
            }
        }
    }
 
 
 
    publicstaticvoidswap(char[]chars, inti,intj) {
        chartemp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
 
    publicstaticvoidmain(String[] args) {
       Scanner sc = newScanner(System.in);
        String text = sc.next();
        printallPer(text);
        //String a = "abc";
        //printallPer(a);
    }
}
发表于 2019-04-08 21:20:20 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main()
{
    string str;
    bool isVirgin = true;   //判断是不是第一次
    while(getline(cin,str))
    {
        string result = "";   //结果字符串
        sort(str.begin(), str.end());   //题目中给出的字符串不一定是升序,有个测试点是aA,所以我们自己先升序排列一遍
        do{
            if(isVirgin)
            {
                result += "[" + str;
                isVirgin = false;
            }
            else
            {
                result += ", " + str;  //注意逗号后面有个空格
            }
        }while(next_permutation(str.begin(),str.end()));   //全排列
        result += "]";
        cout << result << endl;
    }
    return 0;
}
编辑于 2019-06-28 22:50:49 回复(1)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {

    //标准的全排列问题,有重复的全排列,偷懒的就用set去重,答案要求字典顺序输出,就用TreeSet咯,
    static TreeSet<String> output = new TreeSet<>();
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String s = bf.readLine();
        backtrack(s.toCharArray(), 0, s.length());
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (String item : output) {
            sb.append(item).append(",").append(" ");
        }
        System.out.println(sb.substring(0, sb.length() - 2) + "]");
    }
    //回溯算法
    private static void backtrack(char[] chars, int first, int n) {
        if (first == n) {
            output.add(String.valueOf(chars));
            return;
        }
        for (int i = first; i < n; i++) {
            swap(chars, first, i);
            backtrack(chars, first + 1, n);
            //回溯
            swap(chars, first, i);
        }
    }

    private static void swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
}
发表于 2019-08-21 16:26:08 回复(0)
import itertools
ss=input()
mm=sorted(set(map(''.join,itertools.permutations(ss))))
print("[" + ', '.join(mm) + "]")
最后输出‘,’后面还有一个空格,要不然格式不正确

发表于 2020-03-20 22:03:18 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    bool first;
    while(cin>>s){
        first = true;
        string t = "";
        sort(s.begin(), s.end());
        do{
            if(first){
                t = "[" + s;
                first = false;
            }else{
                t += ", " + s;
            }
        }while(next_permutation(s.begin(), s.end()));
        t += "]";
        cout<<t<<endl;
    }
    return 0;
}

发表于 2019-08-10 11:51:39 回复(1)
input_str = input()

def back_track(tmp,l, r, res):
    if l == r:
        res.append(''.join(tmp))
        return
    else:
        cache = set()
        for i in range(l, r + 1):
            if tmp[i] in cache:
                pass
            else:
                cache.add(tmp[i])
                tmp[l], tmp[i] = tmp[i], tmp[l]
                back_track(tmp, l + 1, r, res)
                tmp[l], tmp[i] = tmp[i], tmp[l]

result = []
back_track(list(input_str), 0, len(input_str)-1, result)
# 按字典序打印出
result.sort()
print("[" + ', '.join(result) + "]")

发表于 2023-10-09 20:47:34 回复(0)
import java.util.*;

public class Main {
    public static Set<Stringset=new TreeSet<>();
    public static void main(String[] args) {
       Scanner sc=new Scanner(System.in);
       String str=sc.nextLine();
       test1(str.toCharArray(),0,str.length()-1);
        System.out.println(set);
    }
    public static void test1(char[] arrayint startint end){
        if(start==end){
            set.add(String.valueOf(array));
        }
        for(int i=start;i<=end;i++){
            test2(array,i,start);
            test1(array,start+1,end);
            test2(array,i,start);
        }

    }
    public static void test2(char[] array,int i,int j){
        char temp=array[i];
        array[i]=array[j];
        array[j]=temp;
    }
    // public static String test3(char[] array){
    //  StringBuilder sb=new StringBuilder();
    //  for(char c:array){
    //      sb.append(c);
    //  }
    //    return sb.toString();
    // }

}

发表于 2022-11-13 16:05:03 回复(0)

s = input()
result = []


def p(index, l):
    if len(l) == len(s):
        i_l = "".join([s[i] for i in l])
        if i_l not in result:
            result.append(i_l)
    if index == len(s):
        return

    for i in range(len(s)):
        if i not in l:
            l.append(i)
            p(index + 1, l)
            l.pop()

p(0, [])
result.sort()
print("[",end="")
for i in range(len(result)):
    if i != len(result)-1:
        print(result[i], end=', ')
    else:
        print(result[i], end=']')
发表于 2022-04-23 15:36:52 回复(0)
import itertools
ss=input()
mm=sorted(set(map(''.join,itertools.permutations(ss))))
print("[" + ', '.join(mm) + "]")
发表于 2022-02-15 23:00:02 回复(0)
using System;
using System.Collections.Generic;
using System.IO;
using System.Text;

class Test
{
    static List<string> output = new List<string>();
    static void Main(string[] args)
    {
        string input = Console.ReadLine();

        backtrack(input.ToCharArray(),0 , input.Length);
        
        StringBuilder s = new StringBuilder("[");
        
        delSame();
        
        for(int i = 0;i < output.Count; i++){
            s.Append(output[i]).Append(",").Append(" ");
        }
        s.Remove(s.Length - 2, 2);
        s.Append("]");
        Console.WriteLine(s);
    }
                                            
    private static void backtrack(char[] chars , int first , int n){
        if(first == n){
            output.Add(new string(chars));
            return;
        }
        for(int i = first; i < n; i++){
            swap(chars, first , i);
            backtrack(chars, first + 1, n);
            swap(chars, first , i);
        }
    }
                                            
    private static void swap(char[] chars , int i , int j){
        char temp = chars[j];
        chars[j] = chars[i];
        chars[i] = temp;
    }
    
    private static void delSame(){//去重复
        for (int i = 0; i < output.Count; i++)  //外循环是循环的次数
            {
                for (int j = output.Count - 1 ; j > i; j--)  //内循环是 外循环一次比较的次数
                {

                    if (output[i] == output[j])
                    {
                        output.RemoveAt(j);
                    }

                }
            }
    }
}

发表于 2021-11-06 13:19:56 回复(0)
虽然通过了所有测试用例,但似乎没去重



输出为字符,并且逗号后面有一个空格
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

vector<string> res;

void dfs(string str,int begin)
{
    if(begin==str.size()-1)
    {
        res.push_back(str);
        return ;
    }
    for(int i=begin;i<str.size();i++)
    {
        if(i!=begin&&str[i]==str[begin])
            continue;
        
        swap(str[i],str[begin]);
        dfs(str,begin+1);
        swap(str[i],str[begin]);
    }
    
}
int main()
{
    string str;
    cin>>str;
    dfs(str,0);
    sort(res.begin(),res.end());
    
    string s;
    s+="["+res[0];
    
    for(int i=1;i<res.size();i++)
    {
        s+=", "+res[i];
    }
    s+="]";
    
    cout<<s<<endl;
    return 0;
}






编辑于 2020-08-14 16:52:52 回复(0)
#include<bits/stdc++.h>
using namespace std;
vector<string>res;
string t;
void bk(string s,vector<int>&vis)
{
    if(t.size()==s.size())res.push_back(t);
    for(int i=0;i<s.size();i++)
    {
        if(vis[i]==1)continue;
        if(i>0&&s[i]==s[i-1]&&vis[i-1]==0)continue;
        t.push_back(s[i]);
        vis[i]=1;
        bk(s,vis);
        t.pop_back();
        vis[i]=0;
    }
}
int main()
{
    string s;
    cin>>s;
    sort(s.begin(),s.end());
    vector<int>vis(s.size(),0);
    bk(s,vis);
    cout<<'[';
    for(int i=0;i<res.size()-1;i++)
    {
        cout<<res[i]<<','<<" ";
    }
    cout<<res.back()<<']';
    return 0;
}

发表于 2020-07-24 21:24:58 回复(0)
//深度优先搜索
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <limits.h>
#include <set>

using namespace std;

void DFS_SSP(string s, int k, int m, set<string> &strset) {
    if (k == m) {
        strset.insert(s);
    }
    else {
        for (int i = k; i < m;i++) {
            swap(s[i], s[k]);
            DFS_SSP(s, k+1, m, strset);
            swap(s[i], s[k]);
        }
    }
}

void StringSullPermutation() {
    string s;
    cin>>s;
    int len = s.size();
    set<string> strset; //set自动排序和去重
    DFS_SSP(s, 0, len, strset);
    //输出
    set<string>::iterator it = strset.begin();
    cout << "[";
    while (it != strset.end())
    {
        cout << *it;
        if (++it != strset.end()) {
            cout << ", ";
        }
    }
    cout << "]" <<endl;
}

int main(){
    StringSullPermutation();
    return 0;
}
编辑于 2020-05-14 21:50:36 回复(0)
回溯法  主要在于重复字符的处理
#include<iostream>
(720)#include<string>
#include<vector>
(721)#include<algorithm>

using namespace std;

void BackTrack(string &s, string &temp, vector<string> &ans, vector<bool> &vis){
    if (temp.size() == s.size()){
        ans.push_back(temp);
        return ;
    }
    for (int i = 0; i < s.size(); i++){
        if (vis[i] || (i > 0 && !vis[i-1] && s[i] == s[i-1]))  //控制访问重复或已经访问的字符
            continue;
        vis[i] = true;
        temp.push_back(s[i]);
        BackTrack(s, temp, ans, vis);
        vis[i] = false;
        temp.pop_back();
    }
    return ;
}
int main(void){
    string s;
    cin>>s;
    sort(s.begin(), s.end());
    vector<string> ans;
    string temp;
    vector<bool> vis(s.size(), false);
    BackTrack(s, temp, ans, vis);
    cout<<"[";
    for (int i = 0; i < ans.size(); i++){
        if (i == ans.size()-1)
            cout<<ans[i];
        else
            cout<<ans[i]<<", ";
    }
    cout<<"]"<<endl;
}

发表于 2020-05-10 10:56:12 回复(0)
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;
import java.util.TreeSet;

public class Permutation {
	//华为机试,字符串处理,排列组合
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		String str = input.nextLine();
		List<Character> charList=new ArrayList<Character>();  
        Stack<Character> result=new Stack<Character>();
        TreeSet<String> resultSet = new TreeSet<String>();  //去重加排序
        for(int i = 0;i < str.length();i++){
        	charList.add(str.charAt(i));  
        }
        play(charList,result,resultSet);  
        System.out.println(resultSet);
		input.close();
	}
	
	public static void play(List<Character> charList,Stack<Character> result,TreeSet<String> resultSet){  
      //如果size为1,说明已经排列到最后一个了
      if(charList.size() == 1)  
      {  
    	  result.push(charList.get(0));
    	  resultSet.add(result.toString().replaceAll("[^a-zA-Z]", ""));
          result.pop();  
      }else{  
          for(int i=0;i<charList.size();i++){  
        	  //逐个压栈排列
        	  result.push(charList.get(i));   
              List<Character> tmp=new ArrayList<Character>();  
              for(Character a:charList){
            	  tmp.add(a); 
              }
              //去掉已经压栈的字符
              tmp.remove(i);  
              //排列子序列
              play(tmp,result,resultSet); 
              //移除已排列字符
              result.pop();      
          }  
      }                     
 }  
}

发表于 2020-05-05 11:45:23 回复(0)
还是全排列,只不过,要求最后打印有序,用一个List,存储结果们,然后用list的sort就行了。
//咋又是全排列啊
import java.util.*;
public class Main {
    public ArrayList<String> Permutation(String str) {
        //全排列问题,之前做过哦,是带重复字符的。
        //还记得怎么做的吗
        ArrayList<String> result=new ArrayList<>();
        if(str.length()<=0) return result;
        boolean used[] = new boolean[str.length()];
        char stack[] = new char[str.length()];
        sub(stack,str,0,used,result);
        
        Comparator<String> c = (x,y)->{
            return x.compareTo(y);
        };
        result.sort(c);
        return result;
    }
    private void sub(char stack[],String str,int seat,boolean used[],ArrayList<String> result){
        if(seat==str.length()){
            //把stack变为一个字符串,带重复字符哦
            result.add(new String(stack));
            return;
        }
        for(int i=0;i<str.length();++i){
            if(!used[i]){
                stack[seat]=str.charAt(i);
                used[i]=true;
                sub(stack,str,seat+1,used,result);
                used[i]=false;
                while(i+1<str.length()&&str.charAt(i+1)==str.charAt(i)) i++;//去重
            }
        }
    }
    public static void main(String args[]){
        Scanner scanner = new Scanner(System.in);
        System.out.println(new Main().Permutation(scanner.nextLine()));
        scanner.close();
        //我擦,还有顺序的要求吗?坑人?
        
    }
}


发表于 2020-04-08 13:18:04 回复(0)
TER头像 TER
竟然要输出字符串,出题的人这样搞就没意思了啊。
单次输入 通过
import sys
ss = sys.stdin.readline().strip()
def perm(ss):
    if len(ss) <= 1:
        return [ss]
    ans = set()
    for i in range(len(ss)):
        for j in perm(ss[:i]+ss[i+1:]):
            ans.add(ss[i]+j)
    return sorted(list(ans))
print('[' + ", ".join(perm(ss)) + ']')


循环输入 不通过 ???
import sys
while True:
    try:
        ss = sys.stdin.readline().strip()
        def perm(ss):
            if len(ss) <= 1:
                return [ss]
            ans = set()
            for i in range(len(ss)):
                for j in perm(ss[:i]+ss[i+1:]):
                    ans.add(ss[i]+j)
            return sorted(list(ans))
        print('[' + ", ".join(perm(ss)) + ']')
    except:
        pass


发表于 2020-03-31 17:13:58 回复(0)