判断乱序字符串

scramble-string

http://www.nowcoder.com/questionTerminal/2bdc44bb0186468b8d8c13ea5d3a9e58

牛客的标签里面有“动态规划”,搞得我一脸懵逼😳

本题应该用递归/贪心实现,条件如下:

  1. 基准1: 如果两个字符串长度不相等,返回false
  2. 基准2: 如果两个字符串相等,返回false
  3. 基准3: 如果两个字符串中对应字符的个数不相等,返回false
  4. 递归判断子字符串是否是乱序字符串

代码如下:

//
// Created by jt on 2020/8/30.
//
#include <string>
#include <unordered_map>
using namespace std;

class Solution {
public:
    /**
     *
     * @param s1 string字符串
     * @param s2 string字符串
     * @return bool布尔型
     */
    bool isScramble(string s1, string s2) {
        // write code here
        return dfs(s1, s2);
    }

    bool dfs(string s1, string s2) {
        if (s1.size() != s2.size()) return false;
        if (s1 == s2) return true;
        unordered_map<char, int> um;
        for (int i = 0; i < s1.size(); ++i) {
            ++um[s1[i]]; --um[s2[i]];
        }
        for (auto it = um.begin(); it != um.end(); ++it) {
            if (it->second != 0) return false;
        }

        for (int i = 1; i < s1.size(); ++i) {
            if (dfs(s1.substr(0, i), s2.substr(0, i)) &&
                dfs(s1.substr(i), s2.substr(i))) return true;
            if (dfs(s1.substr(0, i), s2.substr(s1.size()-i)) &&
                    dfs(s1.substr(i), s2.substr(0, s1.size()-i))) return true;
        }
        return false;
    }
};
刷遍天下无敌手 文章被收录于专栏

秋招刷题历程

全部评论
递归复杂度有O(n!)吧,用动态规划也可以做,复杂度是O(n^4)
1 回复 分享
发布于 2020-09-01 13:26

相关推荐

Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
强大的马里奥:不太可能,我校计算机硕士就业率99%
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务