#P3261. 字符串拼接(200分)
-
1000ms
Tried: 183
Accepted: 32
Difficulty: 5
所属公司 :
华为od
字符串拼接(200分)
思路:DFS枚举
这道题的思路其实有点像这道LeetCode题:47. 全排列 II - 力扣(LeetCode)
因为给定的字符串中有重复的字符,因此我们需要对字符串进行排序,然后做一个去重操作
比如给定的字符串是"abba",要求我们生成长度为2的两个字符,那其实只有两种情况:"ab"和"ba",因此需要去除冗余的"ab"和"ba",就需要利用到一些去重的技巧,具体可以参考下面代码。
本题在上面这道LeetCode的题目上,增加了两个条件:构成的新字符串的长度为k以及新字符串的相邻元素不能相等。
JavaScript
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
let inputLines = [];
rl.on('line', (line) => {
inputLines.push(line);
});
rl.on('close', () => {
const [s, k] = inputLines[0].split(' ');
const sArray = s.split('');
sArray.sort(); // 将字符串按照字典序排序,方便后续去重操作
const kInt = parseInt(k);
let ans = 0;
const n = sArray.length;
const vis = Array(n).fill(false); // 用于标记当前字符是否被选取
const v = []; // 存储对应的字符串序列
// 定义深度优先搜索函数
function dfs(u) {
if (u === kInt) {
ans += 1;
return;
}
for (let i = 0; i < n; i++) {
// 如果当前字符已经被使用过,或者与上一个字符一样(但上一个字符未被使用),则跳过
if (vis[i] || (i > 0 && sArray[i] === sArray[i - 1] && !vis[i - 1])) {
continue;
}
// 如果相邻字符相同,则跳过
if (v.length && v[v.length - 1] === sArray[i]) {
continue;
}
// 将当前字符添加到序列中,更新标记,并进行递归
v.push(sArray[i]);
vis[i] = true;
dfs(u + 1);
// 回溯操作,将当前字符弹出序列,还原标记
v.pop();
vis[i] = false;
}
}
// 从起始状态开始深度优先搜索
dfs(0);
// 输出结果
console.log(ans);
});
Java
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static char[] s;
static int k;
static int ans = 0;
static int n;
static boolean[] vis;
static StringBuilder v = new StringBuilder();
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取输入
String input = scanner.nextLine();
String[] inputArray = input.split(" ");
s = inputArray[0].toCharArray();
Arrays.sort(s); // 将字符数组按照字典序排序,方便后续去重操作
k = Integer.parseInt(inputArray[1]);
n = s.length;
vis = new boolean[n]; // 用于标记当前字符是否被选取
// 调用深度优先搜索函数
dfs(0);
// 输出结果
System.out.println(ans);
}
// 定义深度优先搜索函数
static void dfs(int u) {
if (u == k) {
ans++;
return;
}
for (int i = 0; i < n; i++) {
// 如果当前字符已经被使用过,或者与上一个字符一样(但上一个字符未被使用),则跳过
if (vis[i] || (i > 0 && s[i] == s[i - 1] && !vis[i - 1])) {
continue;
}
// 如果相邻字符相同,则跳过
if (v.length() > 0 && v.charAt(v.length() - 1) == s[i]) {
continue;
}
// 将当前字符添加到序列中,更新标记,并进行递归
v.append(s[i]);
vis[i] = true;
dfs(u + 1);
// 回溯操作,将当前字符从序列中移除,还原标记
v.deleteCharAt(v.length() - 1);
vis[i] = false;
}
}
}
Python
# 从输入中读取字符串 s 和整数 k
s, k = input().split()
s = list(s)
s.sort() # 将字符串按照字典序排序,方便后续去重操作
k = int(k)
ans = 0
n = len(s)
vis = [False] * n # 用于标记当前字符是否被选取
v = [] # 存储对应的字符串序列
# 定义深度优先搜索函数
def dfs(u):
if u == k:
nonlocal ans
ans += 1
return
for i in range(n):
# 如果当前字符已经被使用过,或者与上一个字符一样(但上一个字符未被使用),则跳过
if vis[i] or (i > 0 and s[i] == s[i - 1] and not vis[i - 1]):
continue
# 如果相邻字符相同,则跳过
if len(v) and v[-1] == s[i]:
continue
# 将当前字符添加到序列中,更新标记,并进行递归
v.append(s[i])
vis[i] = True
dfs(u + 1)
# 回溯操作,将当前字符弹出序列,还原标记
v.pop()
vis[i] = False
# 从起始状态开始深度优先搜索
dfs(0)
print(ans)
C++
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
string s;
int k;
int ans = 0;
int n;
vector<bool> vis;
string v;
// 定义深度优先搜索函数
void dfs(int u) {
if (u == k) {
ans++;
return;
}
for (int i = 0; i < n; i++) {
// 如果当前字符已经被使用过,或者与上一个字符一样(但上一个字符未被使用),则跳过
if (vis[i] || (i > 0 && s[i] == s[i - 1] && !vis[i - 1])) {
continue;
}
// 如果相邻字符相同,则跳过
if (!v.empty() && v.back() == s[i]) {
continue;
}
// 将当前字符添加到序列中,更新标记,并进行递归
v.push_back(s[i]);
vis[i] = true;
dfs(u + 1);
// 回溯操作,将当前字符弹出序列,还原标记
v.pop_back();
vis[i] = false;
}
}
int main() {
// 读取输入
cin >> s >> k;
sort(s.begin(), s.end()); // 将字符串按照字典序排序,方便后续去重操作
n = s.length();
vis = vector<bool>(n, false); // 用于标记当前字符是否被选取
// 从起始状态开始深度优先搜索
dfs(0);
// 输出结果
cout << ans << endl;
return 0;
}
题目描述
给定 M 个字符( a-z ) ,从中取出任意字符(每个字符只能用一次)拼接成长度为 N 的字符串,要求相同的字符不能相邻。
计算出给定的字符列表能拼接出多少种满足条件的字符串,输入非法或者无法拼接出满足条件的字符串则返回 0 。
输入描述
给定长度为 M 的字符列表和结果字符串的长度 N ,中间使用空格(" ")拼接。
- 0<M<30
- 0<N≤5
输出描述
输出满足条件的字符串个数。
示例1
输入
abc 1
输出
3
说明:
给定的字符为 abc ,结果字符申长度为 1 ,可以拼接成 a、b、c ,共 3 种。
示例2
输入
dde 2
输出
2
说明:
给定的字符为 dde ,果字符串长度为 2 ,可以拼接成 de、ed, 共 2 种。