字符串全排列

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)

#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;
}

我的思路就是用回溯深搜求出全排列的所有情况，然后再和输入比较，求出所有确少的，但最终只过了 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;
    }
}

array_diff

$b = ['BAC','ABC','BCA','AAA','BBB']; //替换数据 $c = ['BAC','ABC','BCA','AAA'];  $D=array_diff($b,$c);  var_dump($D);

//提交通过只有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));

不知道什么原因,通过率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);
	}
}

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();
    }
}

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)

# 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)