专栏首页AI那点小事剑指offer——字符串的排列

剑指offer——字符串的排列

概述

题目描述 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 输入描述: 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。


思路

这是一道典型回溯法的题目,类似于八皇后。利用dfs进行求解。由于可能出现重复字符串,因此必须将中间结果存入集合后转入vector中,最后进行排序。


C++ AC代码

#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

class Solution {
    public:
        vector<string> Permutation(string str) {
            char* ch = (char*)str.c_str();
            int len = str.length();
            vector<string> ans; 
            set<string> s;
            if(str == ""){
                return ans;
            }
            dfs(s,str,len,0);
            for(set<string>::iterator it = s.begin() ; it != s.end() ; it++){
                ans.push_back(*it);
            }
            sort(ans.begin(),ans.end());
            return ans;
        }

        void dfs(set<string>& s,string str,int len,int cnt){
            if(cnt == len){
                s.insert(str);
            }else{
                for(int i = cnt ; i < len ; i++){
                    char tmp = str[cnt];
                    str[cnt] =str[i];
                    str[i] = tmp;
                    dfs(s,str,len,cnt+1);
                    tmp = str[cnt];
                    str[cnt] =str[i];
                    str[i] = tmp;
                }
            }
        }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剑指offer——把字符串转换成整数

    题目描述 将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能,但是string不符合数字要求时返回0),要求不能使用字符串...

    AI那点小事
  • 剑指offer--替换空格

    请实现一个函数,将一个字符串中的空格替换成“%20”。 例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

    AI那点小事
  • 变换次数

    牛牛想对一个数做若干次变换,直到这个数只剩下一位数字。 变换的规则是:将这个数变成 所有位数上的数字的乘积。比如285经过一次变换后转化成2*8*5=80....

    AI那点小事
  • Python3 与 C# 基础语法对比(String专栏-新排版)

    在线编程:https://mybinder.org/v2/gh/lotapp/BaseCode/master

    逸鹏
  • 【leetcode刷题】T90-转换成小写字母

    实现函数 ToLowerCase(),该函数接收一个字符串参数 str,并将该字符串中的大写字母转换成小写字母,之后返回新的字符串。

    木又AI帮
  • php安装程序制作原理

    过程: 1、(之前需要有安装协议)检查环境(操作系统、php版本、数据库、附件上传、目录权限、特殊环境要求(pdo、rewrtie、gd2、短标签等)) 2...

    苦咖啡
  • 去除字符数组中指定的字符

    Winter_world
  • C#字符串截取

    yaphetsfang
  • LeetCode 709. 转换成小写字母

    实现函数 ToLowerCase(),该函数接收一个字符串参数 str,并将该字符串中的大写字母转换成小写字母,之后返回新的字符串。

    Michael阿明

扫码关注云+社区

领取腾讯云代金券