劍指Offer系列(java版,詳細解析)38.字符串的排列

程序員社區 2022-01-08 02:58:27 阅读数:621

offer 系列 java 解析 字符串

題目描述

劍指 Offer 38. 字符串的排列

難度中等237收藏分享切換為英文接收動態反饋

輸入一個字符串,打印出該字符串中字符的所有排列。

你可以以任意順序返回這個字符串數組,但裏面不能有重複元素。

示例:

輸入:s = "abc"輸出:["abc","acb","bac","bca","cab","cba"]

限制:

1 <= s 的長度 <= 8

測試用例

  • 功能測試(輸入的字符串中有一個或者多個字符)
  • 特殊輸入測試(輸入的字符串的內容為空或者空指針)

題目考點

  • 考察應聘者的思維能力。
  • 考察應聘者對遞歸的理解和編程能力。

解題思路

通過將字符串分成兩部分,從而把大問題分解成小問題,然後使用遞歸解决。

  1. 求所有可能出現在第一比特置的字符,即把第一個字符和後面所有的字符交換。(記得為了下一次的交換,要把之前交換的東西交換回來)
  2. 固定第一個字符,求後面所有字符的排列。
  3. 這時候我們仍把後面的所有字符分成兩個部分:後面字符的第一個字符,以及這個字符之後的所有字符。重複過程1,2。

參考解題

class Solution {
 List<String> res = new LinkedList<>(); char[] c; public String[] permutation(String s) {
 c = s.toCharArray(); dfs(0); return res.toArray(new String[res.size()]); } void dfs(int x) {
 if(x == c.length - 1) {
 res.add(String.valueOf(c)); // 添加排列方案 return; } HashSet<Character> set = new HashSet<>(); for(int i = x; i < c.length; i++) {
 if(set.contains(c[i])) continue; // 重複,因此剪枝 set.add(c[i]); swap(i, x); // 交換,將 c[i] 固定在第 x 比特 dfs(x + 1); // 開啟固定第 x + 1 比特字符 swap(i, x); // 恢複交換 } } void swap(int a, int b) {
 char tmp = c[a]; c[a] = c[b]; c[b] = tmp; }}
版权声明:本文为[程序員社區]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201080258269595.html