面试题 08.07:无重复字符串的排列组合

简介: 面试题 08.07:无重复字符串的排列组合


题目

题目连接

无重复字符串的排列组合。编写一种方法,计算某字符串的所有排列组合,字符串每个字符均不相同。

示例1:

输入:S = "qwe"
 输出:["qwe", "qew", "wqe", "weq", "ewq", "eqw"]

示例2:

输入:S = "ab"
 输出:["ab", "ba"]

解题

此题就是全排列的类型

方法一:回溯

class Solution {
public:
    string path;
    vector<string> res;
    void backtracing(string& S,vector<bool>& used){
        if(path.size()==S.size()){
            res.push_back(path);
            return;
        }
        for(int i=0;i<S.size();i++){
            if(used[i]==true) continue;
            used[i]=true;
            path.push_back(S[i]);
            backtracing(S,used);
            path.pop_back();
            used[i]=false;
        }
    }
    vector<string> permutation(string S) {
        vector<bool> used(S.size(),false);
        backtracing(S,used);
        return res;
    }
};

换种写法

class Solution {
public:
    vector<string> permutation(string S) {
        string path;
        vector<string> res;
        vector<bool> used(S.size(),false);
        function<void()> backtracing=[&]{
            if(path.size()==S.size()){
                res.push_back(path);
                return;
            }
            for(int i=0;i<S.size();i++){
                if(used[i]==true) continue;
                used[i]=true;
                path.push_back(S[i]);
                backtracing();
                path.pop_back();
                used[i]=false;
            }
        };
        backtracing();
        return res;
    }
};

相关文章
|
6月前
|
存储
力扣面试经典题之数组/字符串
力扣面试经典题之数组/字符串
52 0
|
3月前
|
安全 Java 编译器
【Java基础面试二十九】、说一说你对字符串拼接的理解
这篇文章讨论了Java中字符串拼接的四种常用方式(使用`+`运算符、`StringBuilder`、`StringBuffer`和`String`类的`concat`方法),每种方式适用的场景,以及在不同情况下的性能考量。
|
3月前
|
Java
【Java基础面试二十八】、使用字符串时,new和““推荐使用哪种方式?
这篇文章讨论了在Java中使用字符串时,推荐使用双引号`""`直接量方式而不是使用`new`操作符,因为`new`会在常量池之外额外创建一个对象,导致更多的内存占用。
|
4月前
|
存储 安全 Java
Java面试题:请解释Java中的字符串和字符串缓冲区?
Java面试题:请解释Java中的字符串和字符串缓冲区?
33 0
|
5月前
|
存储 算法 数据挖掘
深入解析力扣166题:分数到小数(模拟长除法与字符串操作详解及模拟面试问答)
深入解析力扣166题:分数到小数(模拟长除法与字符串操作详解及模拟面试问答)
|
6月前
|
存储 算法 安全
【刷题】 leetcode 面试题 01.06 字符串压缩
来看效果: 非常好!!!过啦!!!
63 5
【刷题】 leetcode 面试题 01.06 字符串压缩
|
6月前
|
索引 Python Go
【python学习】字符串详解,面试必问公司的问题
【python学习】字符串详解,面试必问公司的问题
|
6月前
|
存储 Go 开发者
Golang深入浅出之-Go语言字符串操作:常见函数与面试示例
【4月更文挑战第20天】Go语言字符串是不可变的字节序列,采用UTF-8编码。本文介绍了字符串基础,如拼接(`+`或`fmt.Sprintf()`)、长度与索引、切片、查找与替换(`strings`包)以及转换与修剪。常见问题包括字符串不可变性、UTF-8编码处理、切片与容量以及查找与替换的边界条件。通过理解和实践这些函数及注意事项,能提升Go语言编程能力。
187 0
|
6月前
面试题 01.06. 字符串压缩
面试题 01.06. 字符串压缩
23 0
|
6月前
|
算法 测试技术 索引
力扣面试经典题之数组/字符串(二)
力扣面试经典题之数组/字符串(二)
34 0