首页 > 试题广场 >

字符串全排列

[编程题]字符串全排列
  • 热度指数:1314 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
对K个不同字符的全排列组成的数组,  面试官从中随机拿走了一个, 剩下的数组作为输入,  请帮忙找出这个被拿走的字符串?
比如[“ABC”, “ACB”, “BAC”, “CAB”, “CBA”] 返回 “BCA”

输入描述:
第一行输入整数n,表示给定n个字符串。(n == x!-1,2<=x<=10)
以下n行每行输入一个字符串。


输出描述:
输出全排列缺少的字符串。
示例1

输入

5
ABC
ACB
BAC
CAB
CBA

输出

BCA
C++解法(字符串异或操作
有两点注意事项  :
1. 对^=进行了重载
2. 对n==1的特例做个判断
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
void operator ^=(string &a, string b)    //^=重载,给a一个引用就ok了,你要是同时给b引用也是ok的
{
    int len = a.length();
    for(int i = 0; i < len; ++i)
        a[i] = a[i]^b[i];
}
int main()
{
    int n;
    cin>>n;
    string strOut, temp;
    cin>>temp;
    if(n==1)    //当只给一个字符串的时候,组成字符串的字母一定只有两个,所以你可以调用algorithm的reverse(),或者直接输出temp[1],temp[0]都是ok的
    {
        reverse(temp.begin(), temp.end());
        cout<<temp;
        return 0;
    }
    strOut = temp;
    for(int i = 1; i < n; ++i)
    {
        cin>>temp;
        strOut ^= temp;    //上面我重载了符号^=,如果有不懂得小伙伴去Google一下,他其实和函数重载是一样的,只不过有一些硬性要求。
    }
    cout<<strOut;
    return 0;
}


发表于 2019-10-25 17:40:05 回复(3)
def count_list(in_list, rec_dict={}, rec_list=[]):
    for i in in_list:
        if i in rec_dict:
            rec_dict[i] = rec_dict[i] + 1
        else:
            rec_dict[i] = 1
    for i in rec_dict:
        rec_list.append(rec_dict[i])
    new_dict = {v: k for k, v in rec_dict.items()}
    return new_dict[min(rec_list)]


s = int(input())
temp = []
for i in range(s):
    temp.append(input())


def less_morp(input_list, i):
    temp_result = []
    for j in input_list:
        temp_result.append(j[i])
    result = count_list(temp_result, rec_dict={}, rec_list=[])
    return result


result_list = []
if len(temp) == 1:
    str = temp[0][::-1]
else:
    for x in range(len(temp[0])):
        result_list.append(less_morp(input_list=temp, i=x))
        str = "".join(result_list)
print(str)

发表于 2019-09-04 20:40:37 回复(0)
cdf头像 cdf
调用c++库函数next_permutation求下一个排列,然后对排序后的输入进行比较找到缺少的哪一个
#include <bits/stdc++.h>
using namespace std;
int n;
int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    vector<string> strs(n);;
    for (int i=0;i<n;i++){
        cin>>strs[i];
    }
    sort(strs.begin(),strs.end());
    string ns=strs[0];
    sort(ns.begin(),ns.end());
    for (auto s:strs){
        if(ns!=s){
            cout<<ns<<endl;
            return 0;
        }
        next_permutation(ns.begin(),ns.end());
    }
    cout<<ns<<endl;
    return 0;
}


发表于 2020-03-03 14:22:54 回复(0)
#include<stdio.h>
#include<stdlib.h>
int main()
{
    int n, len;
    char s[11];
    char s1[11];
    scanf("%d\n", &n);
    for (int i = 0; i < n; i++)
    {
        gets(s);
        len = strlen(s);
        //printf("%d\n", len);
        if (n == 1)
        {
            s1[0] = s[1];
            s1[1] = s[0];
            s1[len] = '\0';
            int len1 = strlen(s1);
            printf("%s", s1);
            return 0;
        }
        else
        {
                if (i == 0)
                    for (int i = 0; i < len+1; i++)
                    {
                        s1[i] = s[i];
                    }
                else
                {
                    for (int j = 0; j < len; j++)
                    {
                        s1[j] = s1[j] ^ s[j];
                    }
                }
            
        }
    }
    printf("%s", s1);
    return 0;
}
发表于 2019-09-22 22:36:48 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    string s, s0;
    if (n == 1){
        cin >> s;
        string s0 = s;
        for(int i = 0; i < s.size(); i++){
            s0[i] = s[s.size()-i-1];
        }
        cout << s0;
        return 0;
    }
    for(int i = 0; i < n; i++){
        cin >> s;
        if (i == 0) {
            s0 = s;
        } else {
            for (int j = 0; j < s.size(); j++){
                s0[j] = s0[j] ^ s[j];
            }
        }
    }
    cout << s0;
    return 0;
}
因为长为x的字符串必然有x!种排序方式,且x!必为偶数,s[i]相同也是偶数次,使用异或运算,a^a=0,所以除了被拿走的字符,其它都抵消了,最终s0就是结果(表达有点不清楚,大概就这个意思)

发表于 2019-09-06 11:31:26 回复(1)
 java使用异或还是超时了,case只通过了95%,求大佬解惑
public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int nums = scanner.nextInt();
        String[] combines = new String[nums];
        scanner.nextLine();
        combines[0] = scanner.nextLine();
        int char_count = combines[0].length();
        char[] result = new char[char_count];
        if(nums == 1) {
            result[0] = combines[0].charAt(1);
            result[1] = combines[0].charAt(0);
        }else {
            result = combines[0].toCharArray();
        }
        for (int i = 1; i < nums; i++) {
            combines[i] = scanner.nextLine();
            for (int j = 0; j < char_count; j++) {
                result[j] ^= combines[i].charAt(j);
            }
        }
        System.out.println(result);
        scanner.close();
    }
}
发表于 2019-09-11 12:51:41 回复(0)
java 100%
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int lines = scanner.nextInt();
        scanner.nextLine();
        StringBuilder input = new StringBuilder();
        for (int i = 0; i < lines; i++) {
            input.append(scanner.nextLine());
        }
        if (lines == 1) {
            System.out.println(input.substring(1, 2) + input.substring(0, 1));
            return;
        }
        char[] inputCharArray = input.toString().toCharArray();
        int len = inputCharArray.length / lines;//一个字符串有多长
        StringBuilder res = new StringBuilder();
        for (int j = 0; j < len; j++) {
            char temp = 0;
            for (int k = j; k <inputCharArray.length ; k+=len) {
                temp ^= inputCharArray[k];
            }
            res.append(temp);
        }
        System.out.println(res.toString());
    }
 
}


发表于 2019-09-12 23:48:40 回复(6)

我的思路就是用回溯深搜求出全排列的所有情况,然后再和输入比较,求出所有确少的,但最终只过了 95% ,对比楼上 AC 老哥和同学的讨论

我觉得,过不了的原因应该是算法时间复杂度过大,时间复杂度 O(n!) ,楼上老哥是 O(n^2) ,当输入字符有 26 个时,回溯的规模要比楼上老哥大的多了!

欢迎各位同学一起讨论!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        HashSet<String> origiPaths = new HashSet<>();
        String element = "";
        for (int i = 0; i < n; i++) {
            element = bf.readLine();
            origiPaths.add(element);
        }

        char[] arr = element.toCharArray();
        HashSet<String> paths = new HashSet<>();
        boolean[] visited = new boolean[arr.length];
        dfs(arr, 0, "", paths, visited);
        System.out.println(judge(origiPaths, paths));
    }

    private static void dfs(char[] arr,
                            int cur,
                            String path,
                            HashSet<String> paths,
                            boolean[] visited) {
        if (cur == arr.length) {
            paths.add(path);
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                dfs(arr, cur + 1, path + arr[i], paths, visited);
                visited[i] = false;
            }
        }
    }

    private static String judge(HashSet<String> set1, HashSet<String> set2) {
        for (String str : set2) {
            if (!set1.contains(str)) {
                return str;
            }
        }
        return null;
    }
}
发表于 2019-10-27 20:23:14 回复(0)
map统计做法,占用空间较大
#include<iostream>
#include<vector>
#include<map>
#include<cstring>
#include<stack>
using namespace std;
int main(){
    int t;
    while(cin>>t){
        vector<char> ans;
        vector<string> str;
        str.resize(t);
        cin>>str[0];
        int totalchar=str[0].length();
        for(int i=1;i<t;i++){
            cin>>str[i];
        }
        for(int k=0;k<totalchar;k++){
            map<char,int> charmap;
            for(int tmp=0;tmp<totalchar;tmp++){
                charmap[str[0][tmp]]=0;
            }
            for(int j=0;j<t;j++){
                    charmap[str[j][k]]++;
            }
            map<char,int>::iterator iter;
            for(iter=charmap.begin();iter!=charmap.end();iter++){
                if(iter->second!=(t+1)/totalchar)
                    ans.push_back(iter->first);
            }
        }  
        for(int i=0;i<ans.size();i++)
            cout<<ans[i];
        cout<<endl;
    }
}


发表于 2019-10-21 22:41:39 回复(0)
php:
array_diff
$b = ['BAC','ABC','BCA','AAA','BBB']; //替换数据 $c = ['BAC','ABC','BCA','AAA'];  $D=array_diff($b,$c);  var_dump($D);
发表于 2019-10-19 09:03:31 回复(0)
小白直接建个数组打表,简单粗暴过🙃
发表于 2019-10-02 16:49:23 回复(0)
95%
from collections import Counter

def find_lost(string_list):
    char_set = set(string_list[0])
    n = len(char_set)
    # 需要补充只出现一次的那种情况
    if n > 2:
        ll = []
        #整理字符串
        string_list = list(map(list,zip(*string_list)))
        for i in string_list:
            ll.append(Counter(i).most_common(n)[-1][0])
    elif n ==2:
        return "".join(list(string_list[0])[::-1])
    else:
        return None

    return "".join(ll)
if __name__ == '__main__':
    n = int(input())
    string_list = []
    for i in range(n):
        string_list.append(input())
    print(find_lost(string_list))

发表于 2019-09-26 18:27:30 回复(0)
//提交通过只有95%
function noStr(n, arr){
    if(n == 1){
        return arr[0].split('').reverse().join('');
    }
    var chars = arr[0].split('').sort();
    chars.sort();
    arr.sort();
    var temp = 0, m = 0, res = '';
    for(var i=0; i<chars.length; i++){
        var num = 0;
        for(var k=m; k<arr.length; k++){
            if(arr[k].indexOf(chars[i]) == 0){
                num += 1;
            }else{
                m = k;
                break;
            }
        }
        if(temp == 0){
            temp = num;
        }else{
            if(temp > num){
                var arr2 = arr.slice(i*temp, i*temp+num);
                arr2.forEach(function(item, index){
                	arr2[index] = item.slice(1);
                })
                res = chars[i] + noStr(arr2.length, arr2)
                break;
            }else if(temp < num){
                var arr2 = arr.slice((i-1)*num, (i-1)*num+temp);
                arr2.forEach(function(item, index){
                	arr2[index] = item.slice(1);
                })
                res = chars[i-1] + noStr(arr2.length, arr2)
                break;
            }
        }
    }
    return res;
}


let n = Number(readline())
const ret = []
while(line = readline()){
    ret.push(line)
}
console.log(noStr(n, ret));

发表于 2019-09-18 10:18:10 回复(0)
不知道什么原因,通过率95%,用的异或.

import java.util.HashSet; import java.util.Scanner; import java.util.Set; public class Main { public static void main(String[] args) { String result = ""; Scanner sc = new Scanner(System.in); int n = sc.nextInt(); String[] arr = new String[n]; for (int i = 0; i < n; i++) { arr[i] = sc.next(); } sc.close(); if (n==1) { result = String.valueOf(arr[0].charAt(1)) + String.valueOf(arr[0].charAt(0)); }else { Set<Character> charSet = new HashSet<Character>(); char[] chararr = arr[0].toCharArray(); int length = chararr.length; for (int i = 0; i < length; i++) { charSet.add(chararr[i]); } int index = 0; while (index<length) { for (char c : charSet) { char x = c; for (int i = 0; i < arr.length; i++) { x ^= arr[i].charAt(index); } if (x == 0) { result = result.concat(String.valueOf(c)); charSet.remove(c); index+=1; break; } } } } System.out.println(result); } }

编辑于 2019-09-14 21:35:25 回复(0)
import java.util.LinkedList;
import java.util.Scanner;

public class Main
{
    public static void allPermutation(char []c, int start, int end, LinkedList<String> listStr)
    {
        if(start == end)
        {
            listStr.add(String.valueOf(c));
            return;

        }
        else
        {
            for(int i=start; i<=end; i++)
            {
                swap(c, start, i);//相当于固定第i个字符
                allPermutation(c,start+1, end, listStr);//求出这种情况下的所有排列
                swap(c, start, i);//复位
            }
        }
    }

    public static void swap(char[] c, int i, int j)
    {
        char temp;
        temp = c[i];
        c[i] = c[j];
        c[j] = temp;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num  = in.nextInt();
        String[] str = new String[num];
        for(int i=0;i<num;i++){
            str[i] = in.next();
            
        }
        //保存所有的全排列
        LinkedList<String> listStr = new LinkedList<>();
        char []c = str[0].toCharArray();
        int len = c.length;
        allPermutation(c, 0, len-1, listStr);
        //把输入的字符串从全排列中移除,剩下的就是被拿走的
        //System.out.println(list);
        //System.out.println(listStr);
        for(int i=0; i<num; i++)
        {
            listStr.remove(str[i]);
        }
        System.out.println(listStr.get(0));
        in.close();
    }
}
通过率达到90%
发表于 2019-09-12 23:21:32 回复(0)
通过 95% ,python 还是太慢了,没办法直接变更字符串,每次都需要重新创建字符串
def calc():
    if n == 1:
        return l[0][::-1]

    result = ''
    for i in range(len(l[0])):
        temp = 0
        for each in l:
            temp = temp ^ ord(each[i])
        result += chr(temp)
    return result


if __name__ == '__main__':
    l = []
    n = int(input())
    for i in range(n):
        l.append(input())
    result = calc()
    print(result)


发表于 2019-09-09 16:48:35 回复(1)
const perm = function (s) { 
    const result = []
    if (s.length <= 1) {
        return [s]
    } else { 
        for (let i = 0; i < s.length; i++) { 
            var c = s[i]
            var newStr = s.slice(0, i) + s.slice(i + 1)
            var l = perm(newStr)
            for (var j = 0; j < l.length; j++) { 
                var temp = c + l[j]
                result.push(temp)
            }
        }
    }
    return result
}

let n = Number(readline())
const ret = []
while(line = readline()){
    ret.push(line)
}
const result = perm(ret[0])
const set = new Set(ret)
const re = result.filter(item => !set.has(item))
console.log(re[0])
发表于 2019-09-03 15:59:36 回复(0)
# python
# 仅通过85%
def Permutation(ss):
    res = []
    if len(ss) < 2:
        return ss
    for i in range(len(ss)):
        for n in map(lambda x: x+ ss[i], Permutation(ss[:i]+ss[i+1:])):
            if n not in res:
                res.append(n)
    return sorted(res)
if __name__ == '__main__':
    n = int(input())
    tmp = []
    for i in range(n):
        s = input()
        tmp.append(s)
    ss = list(tmp[0])
    res = Permutation(ss)
    for i in res:
        if i not in tmp:
            print(i)

发表于 2019-09-02 21:21:59 回复(0)