题解 | #字符串的排列#

字符串的排列

http://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7

遇到排列组合问题,一般使用回溯法求解。

回溯法模板:

result = {}
 void backtrack(路径, 选择列表):
    if (满足结束条件){
        result.add(路径)
        return
    }
    for (选择 in 选择列表){
        做选择
        backtrack(路径, 选择列表)
        撤销选择
    }
import java.util.*;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        HashSet<String> ans = new HashSet<>();
        ArrayList<Character> list = new ArrayList<>();
        for (int i = 0; i < str.length(); i++) {
            list.add(str.charAt(i));
        }
        backtrack(list,0,str.length(), ans);
        return new ArrayList<>(ans);
    }

    public void backtrack(List<Character> list, int start, int end, HashSet<String> ans) {
        if (start == end) {
            // 收集结果
            String str = "";
            for (int i = 0; i < list.size(); i++) {
                str += list.get(i);
            }
            ans.add(str);
        }
        for (int i = start; i < end; i++) {
            Collections.swap(list, i, start);
            backtrack(list, start + 1, end, ans);
            Collections.swap(list, i, start);
        }
    }
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-11 11:22
怎么这么多逆天求职者,救救我救救我救救我😭
flmz_Kk:哈哈哈哈哈哈,这么多求职者,肯定有那一两个逆天的
点赞 评论 收藏
分享
Lorn的意义:你这种岗位在中国现在要么牛马天天加班,要么关系户进去好吃好喝,8年时间,真的天翻地覆了,对于资本来说你就说一头体力更好的牛马,哎,退伍没有包分配你真的亏了。
点赞 评论 收藏
分享
05-22 09:23
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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