(新卷,200分)- 字符串拼接（Java JS Python C）

(新卷,200分)- 字符串拼接（Java & JS & Python & C）

题目描述

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

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

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

输入描述

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

输出描述

满足条件的字符串个数

用例

题目解析

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

本题的基础是求解排列。

了解的排列的求解后，我们就可以进一步了解不重复的排列求解

而本题只需要在这两题的基础增加：排列中相邻元素不能相同即可。

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin }); var iter = rl[Symbol.asyncIterator](); const readline = async () => (await iter.next()).value; void (async function () { let [s, n] = (await readline()).split(" "); n = parseInt(n); function getResult() { if (s.length < n) { // 无法拼接出满足条件的字符串 return 0; } for (let c of s) { // 输入非法 if (c < "a" || c > "z") return 0; } // 排序cArr，可以方便后面求解全排列时，进行树层去重 const cArr = [...s].sort(); return dfs(cArr, -1, 0, new Array(cArr.length).fill(false), 0); } /** * 全排列求解 * @param {*} cArr 基于cArr数组求解全排列 * @param {*} pre 排列最后一个字符在cArr中的位置 * @param {*} level 排列的长度 * @param {*} used used[i] 用于标记 cArr[i] 元素是否已使用 * @param {*} count 符号要求的排列有几个 * @returns count */ function dfs(cArr, pre, level, used, count) { // 当排列长度到达n，则是一个符合要求的排列 if (level == n) { // 符合要求的排列个数+1 return ++count; } for (let i = 0; i < cArr.length; i++) { // 每个字符只能用一次 if (used[i]) continue; // 相同的字符不能相邻， pre指向前面一个被选择的字符的在cArr中的位置，i指向当前被选择的字符在cArr中的位置 if (pre >= 0 && cArr[i] == cArr[pre]) continue; // 树层去重(去除重复排列) if (i > 0 && cArr[i] == cArr[i - 1] && !used[i - 1]) continue; used[i] = true; count = dfs(cArr, i, level + 1, used, count); used[i] = false; } return count; } console.log(getResult()); })();

Java算法源码

import java.util.Arrays; import java.util.Scanner; public class Main { static String s; static int n; public static void main(String[] args) { Scanner sc = new Scanner(System.in); s = sc.next(); n = sc.nextInt(); System.out.println(getResult()); } public static int getResult() { if (s.length() < n) { // 无法拼接出满足条件的字符串 return 0; } char[] cArr = s.toCharArray(); for (char c : cArr) { // 输入非法 if (c < 'a' || c > 'z') return 0; } // 排序cArr，可以方便后面求解全排列时，进行树层去重 Arrays.sort(cArr); return dfs(cArr, -1, 0, new boolean[cArr.length], 0); } /** * 全排列求解 * * @param cArr 基于cArr数组求解全排列 * @param pre 排列最后一个字符在cArr中的位置 * @param level 排列的长度 * @param used used[i] 用于标记 cArr[i] 元素是否已使用 * @param count 符号要求的排列有几个 * @return count */ public static int dfs(char[] cArr, int pre, int level, boolean[] used, int count) { // 当排列长度到达n，则是一个符合要求的排列 if (level == n) { // 符合要求的排列个数+1 return ++count; } for (int i = 0; i < cArr.length; i++) { // 每个字符只能用一次 if (used[i]) continue; // 相同的字符不能相邻， pre指向前面一个被选择的字符的在cArr中的位置，i指向当前被选择的字符在cArr中的位置 if (pre >= 0 && cArr[i] == cArr[pre]) continue; // 树层去重(去除重复排列) if (i > 0 && cArr[i] == cArr[i - 1] && !used[i - 1]) continue; used[i] = true; count = dfs(cArr, i, level + 1, used, count); used[i] = false; } return count; } }

Python算法源码

# 输入获取 s, n = input().split() n = int(n) # 全排列求解 def dfs(cArr, pre, level, used, count): """ 全排列求解 :param cArr: 基于cArr数组求解全排列 :param pre: 排列最后一个字符在cArr中的位置 :param level: 排列的长度 :param used: used[i] 用于标记 cArr[i] 元素是否已使用 :param count: 符号要求的排列有几个 :return: count """ # 当排列长度到达n，则是一个符合要求的排列 if level == n: # 符合要求的排列个数+1 count += 1 return count for i in range(len(cArr)): # 每个字符只能用一次 if used[i]: continue # 相同的字符不能相邻， pre指向前面一个被选择的字符的在cArr中的位置，i指向当前被选择的字符在cArr中的位置 if pre >= 0 and cArr[i] == cArr[pre]: continue # 树层去重(去除重复排列) if i > 0 and cArr[i] == cArr[i - 1] and not used[i - 1]: continue used[i] = True count = dfs(cArr, i, level + 1, used, count) used[i] = False return count # 算法入口 def getResult(): if len(s) < n: # 无法拼接出满足条件的字符串 return 0 for c in s: if c < 'a' or c > 'z': # 输入非法 return 0 cArr = list(s) # 排序cArr，可以方便后面求解全排列时，进行树层去重 cArr.sort() return dfs(cArr, -1, 0, [False] * len(cArr), 0) # 算法调用 print(getResult())

C算法源码

#include <stdio.h> #include <stdlib.h> #define MAX_SIZE 31 char s[MAX_SIZE]; int s_len; int n; /*! * 全排列求解 * @param pre 排列最后一个字符在cArr中的位置 * @param level 排列的长度 * @param used used[i] 用于标记 s[i] 元素是否已使用 * @param count 符号要求的排列有几个 * @return count */ int dfs(int pre, int level, int used[], int count) { // 当排列长度到达n，则是一个符合要求的排列 if (level == n) { // 符合要求的排列个数+1 return ++count; } for (int i = 0; i < s_len; i++) { // 每个字符只能用一次 if (used[i]) continue; // 相同的字符不能相邻， pre指向前面一个被选择的字符的在s中的位置，i指向当前被选择的字符在s中的位置 if (pre >= 0 && s[i] == s[pre]) continue; // 树层去重(去除重复排列) if (i > 0 && s[i] == s[i - 1] && !used[i - 1]) continue; used[i] = 1; count = dfs(i, level + 1, used, count); used[i] = 0; } return count; } int cmp(const void *a, const void *b) { return *((char *) a) - *((char *) b); } int getResult() { int i = 0; while (s[i] != '\0') { // 输入非法 if (s[i] < 'a' || s[i] > 'z') return 0; i++; } s_len = i; if (s_len < n) { // 无法拼接出满足条件的字符串 return 0; } // 排序s，可以方便后面求解全排列时，进行树层去重 qsort(s, i, sizeof(char), cmp); int used[MAX_SIZE] = {0}; return dfs(-1, 0, used, 0); } int main() { scanf("%s", s); scanf("%d", &n); printf("%d\n", getResult()); return 0; }