首页 > 试题广场 >

旋变字符串

[编程题]旋变字符串

热度指数：605 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一个字符串可以分解为多种二叉树。如果str长度为1，认为不可分解；如果str长度为N(N>1),左半部分长度可以为1~N-1，右半部分为剩下的长度，然后你可以交换左右两部分。并且左右部分可以按照同样的逻辑，继续分解。每一个形成的字符串都可以是原字符串的旋变字符串。现在给你两个字符串str1和str2，判断str2是否为str1的旋变字符串。

输入描述:

输入包括两行，第一行一个字符串，代表str1，第二行一个字符串，代表str2。

输出描述:

如果str2是str1的旋变字符串请输出“YES”，否则输出“NO”。

示例1

输入

abcd
dbac

输出

YES

说明

abcd->d...abc->d...ab...c->d...b...a...c

示例2

输入

IJz
JzI

输出

YES

说明

左边为l右边为Jz交换  变Jzl

备注:

时间复杂度,额外空间复杂度。

算法知识视频讲解

helloxuanbao

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#define MAXLEN 101

bool is_valid(char *str1, char *str2) {
    int char_map[256];
    memset(char_map, 0, sizeof(int) * 256);
    for (int i = 0; i < strlen(str1); i++) {
        char_map[str1[i]]++;
    }
    for (int i = 0; i < strlen(str2); i++) {
        if (--char_map[str2[i]] < 0) {
            return false;
        }
    }
    return true;
}

bool dp[MAXLEN][MAXLEN][MAXLEN];

int main(void) {
    char str1[MAXLEN], str2[MAXLEN];
    scanf("%s%s", str1, str2);
    if (!is_valid(str1, str2)) {
        printf("%s\n", "NO");
        return 0;
    }
    int len1 = (int) strlen(str1);
    int len2 = (int) strlen(str2);
    for (int i = 0; i < len1; i++) {
        for (int j = 0; j < len2; j++) {
            dp[i][j][1] = str1[i] == str2[j];
        }
    }
    for (int s = 2; s <= len1; s++) {
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                for (int ls = 1; ls < s; ls++) {
                    if ((dp[i][j][ls] && dp[i + ls][j + ls][s - ls])
                        || (dp[i][j + s - ls][ls] && dp[i + ls][j][s - ls])) {
                        dp[i][j][s] = true;
                        break;
                    }
                }
            }
        }
    }
    printf("%s\n", dp[0][0][len1] ? "YES" : "NO");
    return 0;
}

发表于 2022-02-14 23:08:21 回复(0)