返回目录

题目描述

给定 M（0 < M ≤ 30）个字符（a-z），从中取出任意字符（每个字符只能用一次）拼接成长度为 N（0 < N ≤ 5）的字符串，

要求相同的字符不能相邻，计算出给定的字符列表能拼接出多少种满足条件的字符串，

输入非法或者无法拼接出满足条件的字符串则返回0。

输入描述

给定的字符列表和结果字符串长度，中间使用空格(" ")拼接

输出描述

满足条件的字符串个数

示例：

题目解析

根据用例2的说明来看，本题是要求解的是：不重复的指定长度的排列。且本题还增加了一个条件，即排列中相邻元素不能相同。

Python算法源码

# Python 3

def dfs(pre, level, used, count):
    global s
    global n
  
    # 当排列长度到达n，则是一个符合要求的排列
    if level == n:
        # 符合要求的排列个数+1
        return count + 1
  
    for i in range(len(s)):
        # 每个字符只能用一次
        if used[i]:
            continue
      
        # 相同的字符不能相邻， pre指向前面一个被选择的字符的在cArr中的位置，i指向当前被选择的字符在cArr中的位置
        if pre >= 0 and s[i] == s[pre]:
            continue
      
        # 树层去重(去除重复排列)
        if i > 0 and s[i] == s[i - 1] and not used[i - 1]:
            continue
      
        used[i] = True
        count = dfs(i, level + 1, used, count)
        used[i] = False
  
    return count

def solution():
    global s
    global n
  
    if len(s) < n:
        # 无法拼接出满足条件的字符串
        return 0
  
    for c in s:
        # 输入非法
        if c < 'a' or c > 'z':
            return 0
  
    # 排序cArr，可以方便后面求解全排列时，进行树层去重
    s = ''.join(sorted(s))
  
    used = [False] * len(s)
    return dfs(-1, 0, used, 0)

if __name__ == "__main__":
    s, n = input().split()
    n = int(n)
    print(solution())

C语言算法源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int n; // 全局变量n，表示要求的排列长度
char s[100]; // 全局变量s，表示输入的字符串

// 深度优先搜索函数，用于求解排列组合
int dfs(char cArr[], int pre, int level, int used[], int count) {
    if (level == n) {
        return ++count; // 当排列长度达到n时，符合要求的排列个数加1
    }

    for (int i = 0; i < strlen(cArr); i++) {
        if (used[i]) continue; // 如果字符已经被使用过，则跳过当前字符
        if (pre >= 0 && cArr[i] == cArr[pre]) continue; // 如果当前字符和前一个字符相同，则跳过当前字符
        if (i > 0 && cArr[i] == cArr[i - 1] && !used[i - 1]) continue; // 树层去重，跳过重复的排列

        used[i] = 1; // 标记当前字符已被使用
        count = dfs(cArr, i, level + 1, used, count); // 递归调用dfs函数，继续求解下一个字符的排列
        used[i] = 0; // 回溯，取消当前字符的标记
    }

    return count; // 返回符合要求的排列个数
}

// 获取符合要求的排列个数
int getResult() {
    if (strlen(s) < n) {
        return 0; // 如果输入字符串长度小于n，则无法满足要求，返回0
    }

    char cArr[100];
    strcpy(cArr, s); // 将输入的字符串复制到字符数组cArr中

    for (int i = 0; i < strlen(cArr); i++) {
        if (cArr[i] < 'a' || cArr[i] > 'z') return 0; // 如果输入的字符不是小写字母，则返回0，表示输入非法
    }

    qsort(cArr, strlen(cArr), sizeof(char), strcmp); // 对字符数组cArr进行排序，便于后续求解全排列时去重

    int used[100] = {0}; // 用于标记字符是否被使用的数组
    return dfs(cArr, -1, 0, used, 0); // 调用深度优先搜索函数，求解符合要求的排列个数
}

int main() {
    scanf("%s", s); // 输入字符串
    scanf("%d", &n); // 输入排列长度n

    printf("%d\n", getResult()); // 输出符合要求的排列个数

    return 0;
}

Java算法源码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static String s;
    static int s_len;
    static int n;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 输入字符串
        s = scanner.next();
        // 所需排列的长度
        n = scanner.nextInt();

        // 打印 getResult() 函数的结果
        System.out.println(getResult());

        scanner.close();
    }

    static int dfs(int pre, int level, int[] used, int count) {
        // 如果当前排列的长度等于 n，则增加 count
        if (level == n) {
            return ++count;
        }

        for (int i = 0; i < s_len; i++) {
            // 如果字符已经被使用，则跳过
            if (used[i] == 1) continue;

            // 如果当前字符与排列中的前一个字符相同，则跳过
            if (pre >= 0 && s.charAt(i) == s.charAt(pre)) continue;

            // 如果当前字符与字符串中前一个未使用的字符相同，则跳过
            if (i > 0 && s.charAt(i) == s.charAt(i - 1) && used[i - 1] == 0) continue;

            // 标记字符为已使用
            used[i] = 1;
            // 递归到下一层
            count = dfs(i, level + 1, used, count);
            // 回溯
            used[i] = 0;
        }

        return count;
    }

    static int getResult() {
        int i = 0;
        // 计算输入字符串的长度
        while (i < s.length()) {
            // 如果字符不是小写英文字母，则返回 0
            if (s.charAt(i) < 'a' || s.charAt(i) > 'z') return 0;
            i++;
        }

        // 将输入字符串的长度赋值给 s_len
        s_len = i;

        // 如果字符串的长度小于所需的排列长度，则返回 0
        if (s_len < n) {
            return 0;
        }

        // 将字符串转换为字符数组并进行排序
        char[] cArr = s.toCharArray();
        Arrays.sort(cArr);

        // 初始化数组，用于标记字符是否被使用
        int[] used = new int[s_len];
        // 执行深度优先搜索以计算排列数
        return dfs(-1, 0, used, 0);
    }
}