【回溯专题】剑指 Offer 38. 字符串的排列

共以下 3 个回答

• 小肸 永久会员 2023年9月17日 上午11:55

  class Solution {
      static List<String> list;
      public String[] permutation(String s) {
          list = new ArrayList<>();
          char[] arr = s.toCharArray();
          Arrays.sort(arr);
          backtracking(arr, new boolean[arr.length], 0, new StringBuilder());
          String[] res = new String[list.size()];
          list.toArray(res);
          return res;
      }
      //index表示本次递归在tmp中需要填充的位置
      private void backtracking(char[] arr, boolean[] visited, int index, StringBuilder tmp) {
          if (index == arr.length) {
              list.add(tmp.toString());
              return;
          }
          //从arr没有使用过的字符选取一个填入tmp[index]，然后继续填充tmp[index + 1]
          for (int i = 0; i < arr.length; i ++) {
              //重复字符使用第一次出现的
              if (visited[i] || (i > 0 && !visited[i - 1] && arr[i] == arr[i - 1])) {
                  continue;
              }
              visited[i] = true;
              tmp.append(arr[i]);
              backtracking(arr, visited, index + 1, tmp);
              visited[i] = false;
              tmp.deleteCharAt(tmp.length() - 1);
          }
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• sincere 普通 2023年9月14日 下午9:46

  • 思路：看题解的，字符串长度为n，固定第一位有n种选择，第二位在第一位固定的情况下有n-1中选择，所以总共是 n(n-1)(n-2)…2*1种情况；排列的字符串不能重复，即在固定某位字符时，保证 “每种字符只在此位固定一次”
  • 复杂度：时间复杂度O(m!n)，空间复杂度O(n^2)。n 为字符串长度

  class Solution {
      char[] str;
      LinkedList<String> res = new LinkedList<>();
  
      public String[] permutation(String s) {
          str = s.toCharArray();
          dfs(0);
          return res.toArray(new String[res.size()]);
      }
  
      void dfs(int x) {
          if (x == str.length - 1) {
              res.add(String.valueOf(str));// 添加排列方案
              return;
          }
          HashSet<Character> set = new HashSet<>();
          for (int i = x; i < str.length; i++) {
              if (set.contains(str[i])) {
                  continue;// 重复的排列，剪枝
              }
              set.add(str[i]);
              swap(i, x);// 交换，将str[i]固定在第x位
              dfs(x + 1);// x位固定的情况下，开始遍历后续的x+1位
              swap(i, x);// 恢复交换
          }
      }
  
      void swap(int a, int b) {
          char tmp = str[a];
          str[a] = str[b];
          str[b] = tmp;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 塔底的仰望 永久会员 2023年9月9日 下午8:08

  没想到怎么剪枝。。。
  时间复杂度O(n*n!),空间O(n)

  class Solution {
      private List<Character> path;
      private List<String> res;
      private boolean[] visited;
  
      public String[] permutation(String s) {
          this.path = new ArrayList<>();
          this.res = new ArrayList<>();
          this.visited = new boolean[s.length()];
  
          char[] arr = s.toCharArray();
          Arrays.sort(arr);
          dfs(arr, 0);
  
          String[] strs = new String[res.size()];
          for (int i = 0; i < res.size(); i++) {
              strs[i] = res.get(i);
          }
  
          return strs;
      }
  
      public void dfs(char[] arr, int k) {
          if (arr.length == k) {
              res.add(listToString(path));
              return ;
          }
  
          //N叉树搜索
          for (int i = 0; i < arr.length; i++) {
              //剪枝
              if (i > 0 && arr[i] == arr[i - 1] && visited[i - 1] == false) {
                  continue;
              }
              if (!visited[i]) {
                  visited[i] = true;
                  path.add(arr[i]);
                  dfs(arr, k + 1);
                  path.remove(path.size() - 1);
                  visited[i] = false;
              }
          }
      }
  
      public String listToString(List<Character> list) {
          StringBuilder sb = new StringBuilder();
          for (int i = 0; i < list.size(); i++) {
              sb.append(list.get(i));
          }
  
          return sb.toString();
      }
  }
  

  0 赞同 0 条回复

  登录以回复