首页 > 试题广场 >

游游的字符重排

[编程题]游游的字符重排
  • 热度指数：247 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
游游定义一个字符串是“好串”，当且仅当该字符串相邻的字符不相等。例如"arcaea"是好串，而"food"不是好串。

游游拿到了一个字符串，她可以将该字符串的各个字符顺序随意打乱。她想知道一共可以生产多少种不同的好串？

输入描述:
一个仅包含小写字母的字符串，长度不超过10。


输出描述:
好串的数量。
示例1

输入

aab

输出

1

说明

只有"aba"这一种好串。
示例2

输入

arc

输出

6
示例3

输入

aaa

输出

0
算法知识视频讲解
添加回答
喜欢白菜头像 喜欢白菜 
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
bool judge(string str)
{
    int i=1;
    while(i<str.size())
    {
        if(str[i]==str[i-1])
            return false;
        ++i;
    }
    return true;
}
int main() {
    string str;
    cin>>str;
    sort(str.begin(),str.end());
    int res=0;
    do {
    res+=judge(str);
    }while (next_permutation(str.begin(), str.end()));
    cout<<res;
}
// 64 位输出请用 printf("%lld")

发表于 2023-06-26 16:54:30 回复(0)
Python
yq19头像 yq19 
inputstr = input()
d = dict()
for ch in inputstr:
    if ch in d:
        d[ch] += 1
    else:
        d[ch] = 1

def fillnewstr(newstr, d, pos) -> int:
    if pos == len(inputstr):
        # print(newstr)
        return 1

    cnt = 0
    for ch in d.keys():
        if d[ch] > 0 and (pos == 0&nbs***bsp;newstr[pos-1] != ch):
            newstr[pos] = ch
            d[ch] -= 1
            cnt += fillnewstr(newstr, d, pos + 1)
            d[ch] += 1
            newstr[pos] = ''
    return cnt

tmp_max = 0
for v in d.values():
    tmp_max = max(v, tmp_max)
if tmp_max == 1:
    cnt = 1
    for i in range(1, len(d) + 1):
        cnt *= i
    print(cnt)
else:
    newstr = [''] * len(inputstr)
    print(fillnewstr(newstr, d, 0))

发表于 2023-10-08 19:50:35 回复(0)
Python
牛客135606377号头像 牛客135606377号

python牛马写法之状态机+记忆化搜索

python暴力过不了，通过优化可以过
思路就是减少遍历的次数 

from collections import Counter

a = input()
b = Counter(a)

def compute_state(state, rest):
    state_list_ans = []
    def inner(state, rest, i=0):
        if rest == 0:
            state_list_ans.append(state)
            return state_list_ans
        if sum([i == 0 for i in state]) < rest:
            return state_list_ans
        l = len(state)
        s = 0
        state_list = list(state)
        while i < l:
            n = state[i]
            if s == 0:
                if n == 0:
                    s = 1
                    i += 1
                elif n == 1:
                    s = 2
                    i += 1
                else:
                    i += 1
            elif s == 1:
                if n == 0:
                    state_list[i - 1] = 1
                    res = inner(tuple(state_list), rest - 1, i - 1)
                    state_list = list(state)
                    i += 1
                elif n == 1:
                    s = 2
                    i += 1
                else:
                    s = 0
                    state_list[i - 1] = 1
                    inner(tuple(state_list), rest - 1, i - 1)
                    state_list = list(state)
                    i += 1
            else:
                if n != 1:
                    s = 0
                i += 1
        if s == 1:
            state_list[i - 1] = 1
            inner(tuple(state_list), rest - 1, i - 1)
        return state_list_ans
    inner(state, rest)
    return state_list_ans


num_list = sorted([b[i] for i in b], reverse=True)

num_dict = {}


def state_trans(state, rest):
    if rest == 0:
        return 1
    if (state, rest) in num_dict:
        return num_dict[(state, rest)]

    num = num_list[-rest]
    next_list = compute_state(state, num)
    s = 0
    for n in next_list:
        next_state = list(n)
        for index, i in enumerate(next_state):
            if i == 1:
                next_state[index] = 2
        s += state_trans(tuple(next_state), rest - 1)
    num_dict[(state, rest)] = s
    return s


print(state_trans(sum(num_list)*(0,), len(num_list)))



发表于 2023-07-29 18:35:30 回复(0)
提交观点

问题信息

来自：2023年携程秋招技术...
难度：
3条回答 1863浏览

热门推荐

相关试题

游游的字符重排

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号