字符串拼接 - 华为OD统一考试(C卷)

OD统一考试（C卷）

分值： 200分

题解： Java / Python / C++

题目描述

给定 M 个字符( a-z ) ，从中取出任意字符(每个字符只能用一次)拼接成长度为 N 的字符串，要求相同的字符不能相邻。

计算出给定的字符列表能拼接出多少种满足条件的字符串，输入非法或者无法拼接出满足条件的字符串则返回 0 。

输入描述

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

• 0 < M < 30
• 0 < N ≤ 5

输出描述

输出满足条件的字符串个数。

示例1

输入：
abc 1

输出：
3

说明：
给定的字符为 abc ，结果字符申长度为 1 ，可以拼接成 a、b、c ，共 3 种。

示例2

输入：
dde 2

输出：
2

说明：
给定的字符为 dde ，果字符串长度为 2 ，可以拼接成 de、ed， 共 2 种。

题解

这个问题是通过回溯法（Backtracking）解决。

回溯法是一种深度优先搜索的算法，它尝试在解空间中逐步构建解，并在发现当前解不符合条件时进行回溯。

对于这个问题，可以考虑从第一个位置开始选择字符，然后在每个位置上选择不同的字符，直到构建出长度为 N 的字符串，同时要满足相邻字符不相同的条件。

具体步骤

1. 定义一个递归函数 solve，参数包括前一个字符 pre 和剩余字符个数 todo。

2. 在 solve 函数中，对于当前位置的每个字符，如果该字符与前一个字符相同，跳过；

3. 否则，选择该字符，将字符数量减一，递归到下一个位置，并将结果加到总数中，然后恢复字符数量。

4. 在 main 函数中，读取输入，检查是否存在非法字符，然后调用 solve 函数计算满足条件的字符串个数。

代码描述

cnt 是一个数组，用于记录每个字符在给定字符串中的出现次数。

在这个问题中，cnt 数组的长度是 26，对应着英文字母表中的 26 个小写字母。数组中的每个元素表示对应字母的出现次数。

在代码中，首先通过遍历输入字符串，统计每个字符的出现次数，然后根据这个数组进行递归计算满足条件的字符串个数。

cnt 的目的是为了方便在递归过程中追踪每个字符的剩余数量，以确保相同的字符不能相邻出现。

在递归的过程中，每次选择一个字符，都会将对应位置的 cnt 减 1，递归完成后再将其加 1，以确保不影响后续的递归分支。

Java

import java.util.Scanner;

/**
 * @author code5bug
 */
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String input = in.next();
        int n = in.nextInt();

        // 是否非法输入
        boolean illegal = false;

        // 每个字符的个数
        int[] cnt = new int[26];
        for (char c : input.toCharArray()) {
            int idx = c - 'a';
            if (0 <= idx && idx < 26) {
                cnt[idx]++;
            } else {
                illegal = true;
            }
        }

        if (illegal) {
            System.out.println