题解 | #字符串的排列#

字符串的排列

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

import java.util.*;
import java.io.*;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        if (str == null) return null;
        char[] nums = str.toCharArray();
        ArrayList<String> list = new ArrayList<>();
        if (nums.length == 0) return list;
        dfs(0, nums, list);
        return list;
    }

    private void dfs(int idx, char[] nums, ArrayList<String> list) {
        // 不能再往下搜索
        if (idx == nums.length) {
            StringBuilder result = new StringBuilder();
            for (char value : nums) {
                result.append(value);
            }
            list.add(result.toString());
            return;
        }

        // 枚举这一层所有可以做出的选择
        Set<Character> set = new HashSet();
        for (int i = idx; i < nums.length; i++) {
            if(set.contains(nums[i])){
                continue;
            }
            set.add(nums[i]);
            swap(nums, idx, i);
            dfs(idx + 1, nums, list);
            swap(nums, idx, i);
        }
    }

    private void swap(char[] nums, int i, int j) {
        char tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

解题思想:DFS标准模块,主要是 枚举这一层所有可以做出的选择

#算法##算法笔记#
全部评论

相关推荐

点赞 评论 收藏
分享
牛客刘北:如果暑期实习是27届的话,你要晚一年才会毕业,企业为什么会等你呢?要搞清时间逻辑呀!27届现在实习只能是在暑假实习,这是日常实习,不是暑期实习。所以多去投日常实习吧,暑期实习肯定不会要你的
点赞 评论 收藏
分享
八股刚起步,看了javaguide,小林coding,还有面渣,感觉面渣是体验最好的,请问只看面渣够用吗,有不完善的需要补吗?
码农索隆:先背最基础的知识,然后理解情景题,现在面试大多数喜欢问情景题,更考验面试者的基础和临场发挥情况
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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