华为OD机试 - 字符串拼接 - 回溯（Java 2024 C卷 200分）

小鱼儿 2024-04-17 10:29 15阅读 0赞

![在这里插入图片描述][986dcebce006483fb6846cb29a3928a7.gif_pic_center]

> 华为OD机试 2024C卷题库疯狂收录中，刷题[**点这里**][Link 1]

### 专栏导读 ###

本专栏收录于[《华为OD机试（JAVA）真题（A卷+B卷+C卷）》][OD_JAVA_A_B_C]。

**刷的越多，抽中的概率越大**，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天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.  使用深度优先搜索（DFS）的方法生成所有可能的满足条件的字符串。
2.  递归遍历每个字符，判断当前字符是否与前一个字符相同，如果相同则跳过。
3.  根据选择或跳过的情况继续向下递归，直到生成长度为 N 的字符串。
4.  统计满足条件的字符串的数量，并输出结果。

### 五、Java算法源码 ###

public class Test04 {
        
        static String str;
        static int N;
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
    
            str = sc.next(); // 读取字符列表
            N = sc.nextInt(); // 读取字符串长度
    
            // 无法拼接出满足条件的字符串，返回0
            if (str.length() < N) {
        
                System.out.println(0);
            }
    
            char[] arr = str.toCharArray();
    
            /**
             * 给定 M 个字符( a-z ) ,只能是小写字母
             */
            for (char c : arr) {
        
                if (c < 'a' || c > 'z') {
        
                    System.out.println(0);
                }
            }
    
            // 对字符列表进行排序
            Arrays.sort(arr);
    
            // 调用DFS进行全排列生成符合条件的字符串
            boolean[] used = new boolean[arr.length];
            System.out.println(dfs(arr, -1, 0, used, 0));
        }
    
        /**
         * @param arr 给定 M 个字符( a-z )
         * @param lastIndex 满足条件的字符串最后一个字符串在arr中的下角标
         * @param len 满足条件的字符串的长度
         * @param used 是否用过
         * @param count 满足条件的字符串数量
         * @return
         */
        public static int dfs(char[] arr, int lastIndex, int len, boolean[] used, int count) {
        
            // 当字符串长度达到要求，符合条件，count+1
            if (len == N) {
        
                return ++count;
            }
    
            for (int 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, len + 1, used, count);
                used[i] = false;
            }
    
            return count;
        }
    }

### 六、效果展示 ###

#### 1、输入 ####

java 3

#### 2、输出 ####

#### 3、说明 ####

满足条件的字符串：

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

![在这里插入图片描述][0bcf6e64d5484409b92c98d11d5a5947.bmp_pic_center]

🏆下一篇：[华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 C卷 200分）][OD_ - _ - _Java 2024 C_ 200]

🏆本文收录于，[华为OD机试（JAVA）真题（A卷+B卷+C卷）][OD_JAVA_A_B_C]

**刷的越多，抽中的概率越大**，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

![在这里插入图片描述][8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]

[986dcebce006483fb6846cb29a3928a7.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/a1957470ba6742eb904112c75d51c19b.gif
[Link 1]: https://blog.csdn.net/guorui_java/article/details/132683473
[OD_JAVA_A_B_C]: https://blog.csdn.net/guorui_java/category_12293298.html
[0bcf6e64d5484409b92c98d11d5a5947.bmp_pic_center]: https://img-blog.csdnimg.cn/direct/0bcf6e64d5484409b92c98d11d5a5947.bmp#pic_center
[OD_ - _ - _Java 2024 C_ 200]: https://blog.csdn.net/guorui_java/article/details/132197477
[8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/4b5ed59e2cbb42c98d45f6a7c3ef3a7d.gif