当前位置：首页 > article >正文

华为OD机试 - 构成指定长度字符串的个数（Python/JS/C/C++ 2024 E卷 100分）

article 2024/9/20 9:21:56

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

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

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

二、输入描述

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

0 < M < 30
0 < N ≤ 5

三、输出描述

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

1、输入

dde 2

2、输出

3、说明

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

四、测试用例

1、输入

java 3

2、输出

3、说明

满足条件的字符串：

[jav, jva, ava, ajv, avj, aja, vja, vaj]

五、解题思路

使用深度优先搜索（DFS）的方法生成所有可能的满足条件的字符串。
递归遍历每个字符，判断当前字符是否与前一个字符相同，如果相同则跳过。
根据选择或跳过的情况继续向下递归，直到生成长度为 N 的字符串。
统计满足条件的字符串的数量，并输出结果。

五、Python算法源码

def dfs(arr, last_index, length, used, count):
    # 当字符串长度达到要求，符合条件，count + 1
    if length == N:
        return count + 1

    for i in range(len(arr)):
        # 用过了 || 相邻的两个字符不可以相同 || 过滤掉重复排列
        if used[i] or (last_index >= 0 and arr[i] == arr[last_index]) or (i > 0 and arr[i] == arr[i - 1] and not used[i - 1]):
            continue

        used[i] = True
        count = dfs(arr, i, length + 1, used, count)
        used[i] = False

    return count


if __name__ == "__main__":
    str_input = input("请输入字符列表：")
    N = int(input("请输入字符串长度："))

    if len(str_input) < N:
        print(0)
        exit()

    arr = list(str_input)

    # 检查字符是否都是小写字母
    for c in arr:
        if c < 'a' or c > 'z':
            print(0)
            exit()

    # 对字符列表进行排序
    arr.sort()

    # 递归调用DFS进行全排列生成符合条件的字符串
    used = [False] * len(arr)
    print(dfs(arr, -1, 0, used, 0))

六、JavaScript算法源码

function dfs(arr, lastIndex, length, used, count) {
    // 当字符串长度达到要求，符合条件，count + 1
    if (length === N) {
        return count + 1;
    }

    for (let i = 0; i < arr.length; i++) {
        // 用过了 || 相邻的两个字符不可以相同 || 过滤掉重复排列
        if (used[i] || (lastIndex >= 0 && arr[i] === arr[lastIndex]) || (i > 0 && arr[i] === arr[i - 1] && !used[i - 1])) {
            continue;
        }

        used[i] = true;
        count = dfs(arr, i, length + 1, used, count);
        used[i] = false;
    }

    return count;
}

function main() {
    const str = prompt("请输入字符列表：");
    N = parseInt(prompt("请输入字符串长度："));

    if (str.length < N) {
        console.log(0);
        return;
    }

    let arr = str.split('');

    // 检查字符是否都是小写字母
    for (let c of arr) {
        if (c < 'a' || c > 'z') {
            console.log(0);
            return;
        }
    }

    // 对字符列表进行排序
    arr.sort();

    // 递归调用DFS进行全排列生成符合条件的字符串
    let used = new Array(arr.length).fill(false);
    console.log(dfs(arr, -1, 0, used, 0));
}

main();

七、C算法源码

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>

int N;

int dfs(char *arr, int lastIndex, int length, bool *used, int count) {
    // 当字符串长度达到要求，符合条件，count+1
    if (length == N) {
        return ++count;
    }

    for (int i = 0; i < strlen(arr); i++) {
        if (used[i] || (lastIndex >= 0 && arr[i] == arr[lastIndex]) || (i > 0 && arr[i] == arr[i - 1] && !used[i - 1])) {
            continue;
        }

        used[i] = true;
        count = dfs(arr, i, length + 1, used, count);
        used[i] = false;
    }

    return count;
}

int main() {
    char str[100];
    printf("请输入字符列表：");
    scanf("%s", str);

    printf("请输入字符串长度：");
    scanf("%d", &N);

    if (strlen(str) < N) {
        printf("0\n");
        return 0;
    }

    // 检查字符是否都是小写字母
    for (int i = 0; i < strlen(str); i++) {
        if (str[i] < 'a' || str[i] > 'z') {
            printf("0\n");
            return 0;
        }
    }

    // 对字符列表进行排序
    qsort(str, strlen(str), sizeof(char), (int (*)(const void *, const void *))strcmp);

    bool used[strlen(str)];
    memset(used, false, sizeof(used));

    // 递归调用DFS进行全排列生成符合条件的字符串
    printf("%d\n", dfs(str, -1, 0, used, 0));

    return 0;
}

八、C++算法源码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;

int dfs(vector<char>& arr, int lastIndex, int length, vector<bool>& used, int count) {
    // 当字符串长度达到要求，符合条件，count + 1
    if (length == N) {
        return ++count;
    }

    for (int i = 0; i < arr.size(); i++) {
        if (used[i] || (lastIndex >= 0 && arr[i] == arr[lastIndex]) || (i > 0 && arr[i] == arr[i - 1] && !used[i - 1])) {
            continue;
        }

        used[i] = true;
        count = dfs(arr, i, length + 1, used, count);
        used[i] = false;
    }

    return count;
}

int main() {
    string str;
    cout << "请输入字符列表：";
    cin >> str;

    cout << "请输入字符串长度：";
    cin >> N;

    if (str.length() < N) {
        cout << 0 << endl;
        return 0;
    }

    vector<char> arr(str.begin(), str.end());

    // 检查字符是否都是小写字母
    for (char c : arr) {
        if (c < 'a' || c > 'z') {
            cout << 0 << endl;
            return 0;
        }
    }

    // 对字符列表进行排序
    sort(arr.begin(), arr.end());

    // 递归调用DFS进行全排列生成符合条件的字符串
    vector<bool> used(arr.size(), false);
    cout << dfs(arr, -1, 0, used, 0) << endl;

    return 0;
}