字符串拼接 - 华为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 cntif todo == 0:return 1tot = 0for i in range(26):if cnt[i] == 0 or i == pre:  # 前一个字符和当前字符相同或者没有字符了，跳过continue# 选择当前字符，剩余字符数-1，递归求解求和，恢复字符数量cnt[i] -= 1tot += solve(i, todo - 1)cnt[i] += 1return totif __name__ == "__main__":s, n = input().split()n = int(n)illegal = False# 每个字符的个数cnt = [0] * 26for c in s:idx = ord(c) - ord('a')if 0 <= idx < 26:cnt[idx] += 1else:illegal = Trueif 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;
}