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

OD统一考试（C卷）

分值： 200分

题解： Java / Python / C++

alt

题目描述

给定 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 的字符串，同时要满足相邻字符不相同的条件。

具体步骤

定义一个递归函数 solve，参数包括前一个字符 pre 和剩余字符个数 todo。
在 solve 函数中，对于当前位置的每个字符，如果该字符与前一个字符相同，跳过；
否则，选择该字符，将字符数量减一，递归到下一个位置，并将结果加到总数中，然后恢复字符数量。
在 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(0);
        } else {
            System.out.println(solve(cnt, -1, n));
        }
    }

    /**
     * @param cnt  字符个数统计
     * @param pre  前一个字符的下标
     * @param todo 剩余的字符个数
     * @return 组合数量
     */
    static int solve(int[] cnt, int pre, int todo) {
        // 组合成功
        if (todo == 0) return 1;

        int tot = 0;
        for (int i = 0; i < 26; i++) {
            // 前一个字符和当前字符相同或者没有字符了，跳过
            if (cnt[i] == 0 || i == pre) continue;

            // 选择当前字符，剩余字符数-1，递归求解求和，恢复字符数量
            cnt[i]--;
            tot += solve(cnt, i, todo - 1);
            cnt[i]++;
        }
        return tot;
    }
}

Python

def solve(pre: int, todo: int) -> int:
    """
    :param pre: 前一个字符的下标
    :param todo: 剩余的字符个数
    :return: 组合数量
    """
    global cnt
    if todo == 0:
        return 1

    tot = 0
    for i in range(26):
        if cnt[i] == 0 or i == pre:  # 前一个字符和当前字符相同或者没有字符了，跳过
            continue

        # 选择当前字符，剩余字符数-1，递归求解求和，恢复字符数量
        cnt[i] -= 1
        tot += solve(i, todo - 1)
        cnt[i] += 1
    return tot


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

    illegal = False

    # 每个字符的个数
    cnt = [0] * 26
    for c in s:
        idx = ord(c) - ord('a')
        if 0 <= idx < 26:
            cnt[idx] += 1
        else:
            illegal = True

    if illegal:
        print(0)
    else:
        print(solve(-1, n))

C++

#include <iostream>

using namespace std;

int cnt[26]; // 全局变量，每个字符的个数

int solve(int pre, int todo) {
    if (todo == 0) {
        return 1;
    }

    int tot = 0;
    for (int i = 0; i < 26; ++i) {
        if (cnt[i] == 0 || i == pre) { // 前一个字符和当前字符相同或者没有字符了，跳过
            continue;
        }

        // 选择当前字符，剩余字符数-1，递归求解求和，恢复字符数量
        cnt[i]--;
        tot += solve(i, todo - 1);
        cnt[i]++;
    }
    return tot;
}

int main() {
    string s;
    int n;

    cin >> s >> n;

    bool illegal = false;

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

    if (illegal) {
        cout << 0 << endl;
    } else {
        cout << solve(-1, n) << endl;
    }

    return 0;
}