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

题目描述

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

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

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

输入描述

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

输出描述

满足条件的字符串个数

用例

题目解析

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

本题的基础是求解排列。关于排列的求解可以看下：

了解的排列的求解后，我们就可以进一步了解不重复的排列求解，具体可以看下：

LeetCode – 47 全排列 II_leetcode 全排列2-CSDN博客

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

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] != '') {
        // 输入非法
        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("%dn", getResult());

    return 0;
}