跳至主要內容

【回溯】2024E-字符串拼接

【回溯】2024E-字符串拼接

题目描述与示例

本题练习地址：https://www.algomooc.com/problem/P3808

题目描述

给定M (0<M<=30)个字符(a-z)，从中取出任意字符(每个字符只能用一次)拼接成长度为N (0<N<=5)的字符串，要求相同的字符不能相邻，计算出给定的字符列表能拼接出多少种满足条件的字符串，输入非法或者无法拼接出满足条件的字符串则返回0。

输入描述

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

输出描述

满足条件的字符串个数

示例一

输入

abc 1

输出

3

说明

给定的字符为abc，结果字符串长度为1，可以拼接成a,b,c，共3种

示例二

输入

aabc 3

输出

8

说明

给定的字符为aabc，结果字符串长度为3，可以拼接成abc,acb,bac,bca,cba,cab,aba,aca，共8种

解题思路

本题数据量不大，虽然只是要求枚举数量而不是枚举具体的字符串，但仍然可以通过回溯来解决。

注意到在本题中，原输入字符串s中的字符顺序并不重要，只有出现次数是关键信息。

所以很容易考虑应该使用哈希表计数器来统计s中各个字符出现的次数。即

cnt = Counter(s)

回溯的重点在于回溯函数的编写。函数传参需要包含三个参数：

  • n：目标字符串的长度
  • path：当前所选择的路径字符串的情况
  • cnt：原字符串s中的字符剩余情况

考虑递归终止条件，显然当len(path) == n时，我们找到了一个长度为n的拼接字符串，更新ans并退出递归，即

global ans
if len(path) == n:
    ans += 1
    return

考虑横向遍历过程，我们需要考虑cnt中的所有key以及这些key的value。当

  • value == 0时，说明key这个字符已经在之前被选择过了，无法再选
  • (path and key == path[-1])时，说明此时key和当前path的最后一个字符一致，此时是不能够选择key延长在path的后面的。

对于上述两种情况，都可以直接跳过该(key, value)对。

当不满足上述情况时，则可以进行状态更新和回溯，以及回溯结束后的回滚操作。即

for k, v in cnt.items():
    if v == 0 or (path and k == path[-1]):
        continue
    cnt[k] -= 1
    dfs(cnt, path + k, n)
    cnt[k] += 1

综上整体的回溯函数为

def dfs(cnt, path, n):
    global ans
    if len(path) == n:
        ans += 1
        return
    for k, v in cnt.items():
        if v == 0 or (path and k == path[-1]):
            continue
        cnt[k] -= 1
        dfs(cnt, path + k, n)
        cnt[k] += 1

这就完成了本题的核心递归函数。

至于递归入口，则传入path = ""即可。

另外题目说明当出现非法输入时需要返回0，因此还需要判断s中的每一个字符是否均为小写字符。

PS：感兴趣的同学可以思考一下如何使用dp完成这个问题

代码

Python

# 题目：【回溯】2024E-字符串拼接
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：回溯
# 代码看不懂的地方，请直接在群上提问


from collections import Counter


# 回溯的函数
# path是列表或者字符串均可，这里path选择字符串
def dfs(cnt, path, n):
    global ans
    # path长度已经为n，找到了一个答案
    if len(path) == n:
        ans += 1
        return
    # 横向遍历，考虑字符k以及其剩余个数v
    for k, v in cnt.items():
        # 如果剩余个数为0，或者k和path前一个字符一样，则直接跳过k
        if v == 0 or (path and k == path[-1]):
            continue
        # 状态更新：选择k，所以k的的剩余个数-1
        cnt[k] -= 1
        # 回溯：path的末尾要加上k这个字符来作为新的path
        dfs(cnt, path + k, n)
        # 回滚：把选择的这个k还回去，所以k的剩余个数+1
        cnt[k] += 1

# 有可能存在输入非法的情况，所以使用try-except语句
try:
    # 输入字符串s，答案字符的长度n
    s, n = input().split()
    n = int(n)
    # 使用哈希表统计s种每一个字符出现的次数
    # 显然，s中字符的出现顺序不重要
    cnt = Counter(s)
    # 如果s中的字符出现非小写字母的情况（非法输入），输出0
    # 只有全为小写字母，才可以进行回溯过程
    if all("a" <= k <= "z" for k in cnt):
        ans = 0
        dfs(cnt, "", n)
        print(ans)
    else:
        print(0)
except:
    print(0)

Java

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    static int ans = 0;

    // 回溯的函数
    static void dfs(Map<Character, Integer> cnt, StringBuilder path, int n) {
        // path长度已经为n，找到了一个答案
        if (path.length() == n) {
            ans++;
            return;
        }
        // 横向遍历，考虑字符k以及其剩余个数v
        for (char k : cnt.keySet()) {
            int v = cnt.get(k);
            // 如果剩余个数为0，或者k和path前一个字符一样，则直接跳过k
            if (v == 0 || (path.length() > 0 && k == path.charAt(path.length() - 1))) {
                continue;
            }
            // 状态更新：选择k，所以k的的剩余个数-1
            cnt.put(k, v - 1);
            // 回溯：path的末尾要加上k这个字符来作为新的path
            dfs(cnt, new StringBuilder(path).append(k), n);
            // 回滚：把选择的这个k还回去，所以k的剩余个数+1
            cnt.put(k, v);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        String[] parts = input.split(" ");
        String s = parts[0];
        int n = Integer.parseInt(parts[1]);
        Map<Character, Integer> cnt = new HashMap<>();
        for (char ch : s.toCharArray()) {
            cnt.put(ch, cnt.getOrDefault(ch, 0) + 1);
        }
        // 如果s中的字符出现非小写字母的情况（非法输入），输出0
        // 只有全为小写字母，才可以进行回溯过程
        boolean valid = true;
        for (char ch : cnt.keySet()) {
            if (ch < 'a' || ch > 'z') {
                valid = false;
                break;
            }
        }
        if (valid) {
            ans = 0;
            dfs(cnt, new StringBuilder(), n);
            System.out.println(ans);
        } else {
            System.out.println(0);
        }
    }
}

C++

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

int ans = 0;

// 回溯的函数
void dfs(unordered_map<char, int>& cnt, string path, int n) {
    // path长度已经为n，找到了一个答案
    if (path.length() == n) {
        ans++;
        return;
    }
    // 横向遍历，考虑字符k以及其剩余个数v
    for (auto& kv : cnt) {
        char k = kv.first;
        int v = kv.second;
        // 如果剩余个数为0，或者k和path前一个字符一样，则直接跳过k
        if (v == 0 || (!path.empty() && k == path.back())) {
            continue;
        }
        // 状态更新：选择k，所以k的的剩余个数-1
        cnt[k]--;
        // 回溯：path的末尾要加上k这个字符来作为新的path
        dfs(cnt, path + k, n);
        // 回滚：把选择的这个k还回去，所以k的剩余个数+1
        cnt[k]++;
    }
}

int main() {
    string input;
    getline(cin, input);
    string s;
    int n;
    size_t pos = input.find(' ');
    s = input.substr(0, pos);
    n = stoi(input.substr(pos + 1));
    unordered_map<char, int> cnt;
    for (char ch : s) {
        cnt[ch]++;
    }
    // 如果s中的字符出现非小写字母的情况（非法输入），输出0
    // 只有全为小写字母，才可以进行回溯过程
    bool valid = true;
    for (auto& kv : cnt) {
        char ch = kv.first;
        if (ch < 'a' || ch > 'z') {
            valid = false;
            break;
        }
    }
    if (valid) {
        ans = 0;
        dfs(cnt, "", n);
        cout << ans << endl;
    } else {
        cout << 0 << endl;
    }
    return 0;
}

C

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

// 全局变量 ans 记录符合条件的方案数
int ans = 0;

// 回溯函数
// cnt 是每个字符的剩余个数，path 是当前拼接的字符串，n 是目标长度
void dfs(int *cnt, char *path, int path_len, int n, char *unique_chars) {
    // 如果当前 path 的长度达到了目标长度 n，找到一个答案
    if (path_len == n) {
        ans++;
        return;
    }
    // 横向遍历，考虑字符 k 以及其剩余个数 v
    for (int i = 0; unique_chars[i] != '\0'; i++) {
        char k = unique_chars[i];
        int index = k - 'a';
        int v = cnt[index];
        
        // 如果剩余个数为0，或者 k 和 path 的前一个字符一样，则直接跳过 k
        if (v == 0 || (path_len > 0 && path[path_len - 1] == k)) {
            continue;
        }
        
        // 状态更新：选择 k，k 的剩余个数 -1
        cnt[index]--;
        path[path_len] = k;
        
        // 回溯：path 的末尾加上 k 这个字符，递归调用 dfs
        dfs(cnt, path, path_len + 1, n, unique_chars);
        
        // 回滚：将选择的 k 还原，所以 k 的剩余个数 +1
        cnt[index]++;
    }
}

int main() {
    char s[21];
    int n;
    
    // 读取输入字符串 s 和目标长度 n
    if (scanf("%s %d", s, &n) != 2) {
        printf("0\n");
        return 0;
    }
    
    // 使用数组 cnt 记录每个字符的出现次数，初始化为 0
    int cnt[26] = {0};
    char unique_chars[27] = {0};  // 用于存储字符串中的唯一字符
    int unique_index = 0;
    
    // 统计 s 中每一个字符出现的次数，并检查是否为小写字母
    for (int i = 0; s[i] != '\0'; i++) {
        if (!islower(s[i])) {
            printf("0\n");
            return 0;
        }
        
        int index = s[i] - 'a';
        if (cnt[index] == 0) {
            unique_chars[unique_index++] = s[i];  // 记录唯一字符
        }
        cnt[index]++;
    }
    
    // 初始化答案变量
    ans = 0;
    
    // 回溯搜索
    char path[21] = {0};  // 临时路径，用于记录当前的字符拼接
    dfs(cnt, path, 0, n, unique_chars);
    
    // 输出结果
    printf("%d\n", ans);
    
    return 0;
}

Node JavaScript

const readline = require("readline").createInterface({
    input: process.stdin,
    output: process.stdout
});

function dfs(cnt, path, n) {
    global.ans = global.ans || 0;
    // path长度已经为n，找到了一个答案
    if (path.length === n) {
        ans += 1;
        return;
    }
    // 横向遍历，考虑字符k以及其剩余个数v
    for (const [k, v] of Object.entries(cnt)) {
        // 如果剩余个数为0，或者k和path前一个字符一样，则直接跳过k
        if (v === 0 || (path && k === path[path.length - 1])) {
            continue;
        }
        // 状态更新：选择k，所以k的的剩余个数-1
        cnt[k] -= 1;
        // 回溯：path的末尾要加上k这个字符来作为新的path
        dfs(cnt, path + k, n);
        // 回滚：把选择的这个k还回去，所以k的剩余个数+1
        cnt[k] += 1;
    }
}

readline.question("", (input) => {
    try {
        const [s, n] = input.split(" ");
        const lengthN = parseInt(n);

        const cnt = {};
        for (const char of s) {
            if (/[a-z]/.test(char)) {
                cnt[char] = (cnt[char] || 0) + 1;
            } else {
                console.log(0);
                readline.close();
                return;
            }
        }

        global.ans = 0;
        dfs(cnt, "", lengthN);
        console.log(ans);
    } catch {
        console.log(0);
    } finally {
        readline.close();
    }
});

Go

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

var ans int

// 回溯函数
func dfs(cnt map[rune]int, path string, n int) {
    // path长度已经为n，找到了一个答案
    if len(path) == n {
        ans++
        return
    }
    // 横向遍历，考虑字符k以及其剩余个数v
    for k, v := range cnt {
        // 如果剩余个数为0，或者k和path前一个字符一样，则直接跳过k
        if v == 0 || (len(path) > 0 && rune(path[len(path)-1]) == k) {
            continue
        }
        // 状态更新：选择k，所以k的的剩余个数-1
        cnt[k]--
        // 回溯：path的末尾要加上k这个字符来作为新的path
        dfs(cnt, path+string(k), n)
        // 回滚：把选择的这个k还回去，所以k的剩余个数+1
        cnt[k]++
    }
}

func main() {
    reader := bufio.NewReader(os.Stdin)
    input, _ := reader.ReadString('\n')
    input = strings.TrimSpace(input)
    parts := strings.Split(input, " ")
    
    if len(parts) != 2 {
        fmt.Println(0)
        return
    }

    s := parts[0]
    n, err := strconv.Atoi(parts[1])
    if err != nil {
        fmt.Println(0)
        return
    }

    cnt := make(map[rune]int)
    for _, char := range s {
        if char >= 'a' && char <= 'z' {
            cnt[char]++
        } else {
            fmt.Println(0)
            return
        }
    }

    ans = 0
    dfs(cnt, "", n)
    fmt.Println(ans)
}

时空复杂度

时间复杂度：O(NT^N)。T为字符集的大小，最多为26。N为目标字符串的长度。状态树的高度为N，叶子节点的数量最多为T^N。

空间复杂度：O(N)。为状态树的高度。

本站内容包括机考真题解析、八股文速记、技术&行为面试指南、真实上岸经验与截图墙。
Copyright © 2025 欧弟算法