首页 > 试题广场 >

旋变字符串

[编程题]旋变字符串
  • 热度指数：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

备注:
时间复杂度,额外空间复杂度。
算法知识视频讲解
添加回答
Java
pein531头像 pein531
这是个范围上尝试的模型，记字符串的总长度为n。如果两个字符串都只有一个字符，那么只要它们两相等，那这两个字符就互为旋变串。如果两个字符串不止一个字符，而是有size个字符（size>1），将字符串分为左右两部分之后，就有如下两种可能性：
  1. 将假设str1左边的字符串长度为leftPart，则右边的长度为size-leftPart。如果str1[0:leftPart-1]和str2[0:leftPart-1]互为旋变串，且str1[leftPart:size-1]和str2[leftPart:size-1]互为旋变串，则整体互为旋变串。
  2. 如果str1[0:leftPart-1]和str2[size-leftPart:size-1]互为旋变串，且str1[leftPart:size]和str2[0:size-leftPart]互为旋变串，则整体互为旋变串。
整体有三个可变参数，因此本质上是个三维的动态规划问题：(1) 考察的字符串长度为size，取值范围是1到n；(2) str1可以从L1位置开始；(3) str2可以从L2位置开始。由于受到到size的限制，(2)和(3)的取值范围均为0到n-size。首先，我们可以写出会超时的暴力递归尝试版本： 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] str1 = br.readLine().toCharArray();
        char[] str2 = br.readLine().toCharArray();
        int n = str1.length;
        if(!isSameAlpha(str1, str2)){      // 检查一下两个字符串是否有相同的字符
            System.out.println("No");
        }else{
            System.out.println(recurrent(str1, str2, 0, 0, n)? "YES": "NO");
        }
    }
    
    private static boolean recurrent(char[] str1, char[] str2, int L1, int L2, int size) {
        // base case字符串长度为1的时候直接判断两个串是否相等就行
        if(size == 1){
            return str1[L1] == str2[L2];
        }
        for(int leftPart = 1; leftPart < size; leftPart++){
            // 尝试左边字符的数量
            if((recurrent(str1, str2, L1, L2, leftPart) && 
                recurrent(str1, str2, L1 + leftPart, L2 + leftPart, size - leftPart)) 
               || (recurrent(str1, str2, L1, L2 + size - leftPart, leftPart) && 
                   recurrent(str1, str2, L1 + leftPart, L2, size - leftPart))){
                return true;
            }
        }
        return false;
    }
    
    private static boolean isSameAlpha(char[] str1, char[] str2) {
        if(str1.length != str2.length) return false;
        HashMap<Character, Integer> map1 = new HashMap<>(), map2 = new HashMap<>();
        for(int i = 0; i < str1.length; i++){
            map1.put(str1[i], map1.getOrDefault(str1[i], 0) + 1);
            map2.put(str2[i], map2.getOrDefault(str2[i], 0) + 1);
        }
        for(char c: map1.keySet()){
            if(!map2.containsKey(c) || map1.get(c) != map2.get(c))
                return false;
        }
        return true;
    }
}
写出递归版本后，改成动态规划的思路就更加清晰，不容易出错 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] str1 = br.readLine().toCharArray();
        char[] str2 = br.readLine().toCharArray();
        int n = str1.length;
        if(!isSameAlpha(str1, str2)){      // 检查一下两个字符串是否有相同的字符
            System.out.println("NO");
        }else{
            System.out.println(dynamicProgramming(str1, str2)? "YES": "NO");
        }
    }
    
    private static boolean dynamicProgramming(char[] str1, char[] str2) {
        int n = str1.length;
        boolean[][][] dp = new boolean[n][n][n + 1];
        // base case考虑的串长度为1时，只要字符相等就是旋变串
        for(int l1 = 0; l1 < n; l1++){
            for(int l2 = 0; l2 < n; l2++){
                dp[l1][l2][1] = str1[l1] == str2[l2];
            }
        }
        for(int size = 2; size <= n; size++){
            for(int l1 = 0; l1 <= n - size; l1++){
                for(int l2 = 0; l2 <= n - size; l2++){
                    for(int leftPart = 1; leftPart < size; leftPart++){
                        if((dp[l1][l2][leftPart] && dp[l1 + leftPart][l2 + leftPart][size - leftPart]) || 
                           (dp[l1][l2 + size - leftPart][leftPart] && dp[l1 + leftPart][l2][size - leftPart])){
                            dp[l1][l2][size] = true;      // 只要有一个leftPart满足旋变串条件就可以break出去
                            break;
                        }
                    }
                }
            }
        }
        return dp[0][0][n];
    }
    
    private static boolean isSameAlpha(char[] str1, char[] str2) {
        if(str1.length != str2.length) return false;
        HashMap<Character, Integer> map1 = new HashMap<>(), map2 = new HashMap<>();
        for(int i = 0; i < str1.length; i++){
            map1.put(str1[i], map1.getOrDefault(str1[i], 0) + 1);
            map2.put(str2[i], map2.getOrDefault(str2[i], 0) + 1);
        }
        for(char c: map1.keySet()){
            if(!map2.containsKey(c) || map1.get(c) != map2.get(c))
                return false;
        }
        return true;
    }
}

编辑于 2021-12-08 22:55:17 回复(0)
提交观点

问题信息

字符串 树
上传者：小小
难度：
1条回答 4417浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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