华为OD机试统一考试D卷C卷 - 构成指定长度字符串的个数 / 字符串拼接( C++ Java JavaScript python C语言)

avatar
作者
猴君
阅读量:5

华为OD机考:OD统一考试D卷+C卷+A卷+B卷+刷题OJ

真题目录:真题目录(D卷 + C卷 + B卷 + A卷) + 考点说明
必刷专栏:最新2024华为OD机试(Java/JS/Py/C/C++)+ OJ
在线OJ :点击立即刷题,模拟真实机考环境
华为OD面试真题精选:华为OD面试真题精选

题目描述:构成指定长度字符串的个数 (本题分值100)

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

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

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

输入描述

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

输出描述

满足条件的字符串个数

用例1

输入

aab 2 

输出

2 

说明

只能构成ab,ba。

用例2

输入

abc 2 

输出

6 

说明

可以构成:ab ac ba bc ca cb 。

解题思路

使用递归和回溯的思想来生成不同的字符串。具体的逻辑如下:

  1. 首先,我们定义一个函数generateDistinctStrings,这个函数接收以下参数:可用字符集s,目标字符串长度length,当前已生成的字符串current,已生成的结果集result,以及一个标记数组used,用来记录每个字符是否已被使用。

  2. generateDistinctStrings函数中,首先检查当前已生成的字符串current的长度是否等于目标长度length。如果等于,说明我们已经生成了一个满足长度要求的字符串,将其添加到结果集result中,然后返回。

  3. 如果当前字符串current的长度还未达到目标长度length,我们就需要继续添加字符。此时,我们遍历可用字符集s中的每一个字符。对于每一个字符,我们首先检查它是否已经被使用(通过查看used数组),以及它是否与current的最后一个字符相同。如果字符已经被使用,或者与current<

广告一刻

为您即时展示最新活动产品广告消息,让您随时掌握产品活动新动态!