算法：回溯法（backtracking）解决寻找给定字符串的所有排序（permutations）问题_Fala Oviara的博客-程序员秘密

技术标签： algorithms  算法  字符串  数据结构  

字符串的所有排序

列出给定字符串的所有排序, 这个问题通常英文中被称作permutations(排列,排序)
而使用的方法为回溯法(backtracking)

具体的操作为：

将字符串的每一位都与字符串中包括自己的每一位进行交换(swap), 直到没有可与之交换的字符的时候, 输出当前的字符串, 并且返回到上一个节点,尝试交换下一个可能的字符. 直到所有的叶节点都被输出, 即得到所有可能的排序.

用可视化来看回溯的解决步骤:
回溯法

整个查找最终output的过程可以看作是一棵树往下延伸的过程,这棵树最终的所有叶子节点才是我们关心的输出. 在理解完回溯的过程之后, 代码就呼之欲出了. 这里提供js版本的找出所有排序的算法:

/**
 * @param {string} s
 */
var permutations = function(s) {
    
  const length = s.length
  backtracking(s, 0, length - 1)
}

var backtracking = function(s, l, r) {
    
  // 当i和j相同，说明除了自身以外已没有可调换数字，直接输出当前字符串
  if (i === j) {
    
    console.log(s)
  } else {
     // 否则，继续构造回溯树
    for (let i = l; i <= r; i++) {
    
      s = swap(s, l, i)
      backtracking(s, l + 1, r)
      // 把s还原成swap之前的字符串，准备交换下一个字符
      s = swap(s, l, i)
    }
  }
}

// 将字符串a的i和j字符调换位置
var swap = function(a, i, j) {
    
  var charArray = a.split('')
  var tempChar = charArray[i]
  charArray[i] = charArray[j]
  charArray[j] = tempChar
  return charArray.join('')
}
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/qq_35714301/article/details/113503468

智能推荐

(转)Oracle/Mysql/SqlServer函数区别 _yifeixiang的博客-程序员秘密

1.类型转换     --Oracle  select to_number('123') from dual;  --123;   select to_char(33) from dual;       --33;  select to_date('2004-11-27','yyyy/mm/dd') from dual;--2004-11-27    --Mysql  select cast('1...

dbcp数据连接池配置_醇氧的博客-程序员秘密

myBatis连接MySQL报异常：No operations allowed after connection closed.; nested exception is com.mysq 查看了Mysql的文档，以及Connector/J的文档以及在线说明发现，出现这种异常的原因是：　　Mysql服务器默认的“wait_timeout”是8小时，也就是说一个connection空闲超过8个小时，

Ubuntu 配置Android NDK环境_ubuntu 配置ndk环境_氦客的博客-程序员秘密

下载NDK首先，在官网下载相应ndk版本https://developer.android.google.cn/ndk/downloads/older_releases比如 Android NDK, Revision 10e (May 2015)解压缩将下载后的文件放到相关目录下，然后执行./android-ndk-r10e-linux-x86_64.bin 会自动解压缩，生成............

Mybatis的多表操作与注解开发_xghdxdb的博客-程序员秘密

一、Mybatis多表操作1.一对一查询

过拟合和欠拟合概念的详细讲解_weixin_43437893的博客-程序员秘密

课前小例子各位同学上一节课我们讲解了一个多分类的问题，让我们从现在开始会讲一些在深度学习中间时候的一些小技巧这些小技巧可是帮助大家理解深度学习一个非常必要的环节，首先我们来看第一个深度学习中存在的一个问题就是过拟合和和欠拟合。在讲解过拟合和和欠拟合之前，我们来讲一个数据的真实的模态，我们把它一个叫做数据的真实分布那么我们来看第一个例子就是房价例子，然后房价的这个x坐标表示它的房子的面积，...

VC2005从开发MFC ActiveX ocx控件到发布到.net网站的全部过程_BeanJoy的博客-程序员秘密

用VS2008开发ActiveX ocx，依照下面这篇教程能成功，

随便推点

分页工具类_sheng_xinjun的博客-程序员秘密

 import java.io.Serializable;import java.util.List;/** * @author sheng */public class Paging&amp;lt;T&amp;gt; implements Serializable { private static final long serialVersionUID = -538351618436...

redis集群配置_无知就要求知的博客-程序员秘密

在两台服务器redis实现集群在两台服务器redis实现集群：描述服务器列表： — A服务器：192.168.4.254 — B服务器：192.168.4.125预期： —-redis进程之间的主从切换，可以实现实例化的主从操作1、cluseter服务需要rub支持。首先安装rub相关服务yum -y install ruby rubygemsrpm -ivh http://yum.p

CVPR 2018迁移学习相关论文_TBYourHero的博客-程序员秘密

元学习论文总结||小样本学习论文总结2017-2019年计算机视觉顶会文章收录 AAAI2017-2019 CVPR2017-2019 ECCV2018 ICCV2017-2019 ICLR2017-2019 NIPS2017-2019https://blog.csdn.net/cp_oldy/article/details/82183813...

UART0串口编程系列 串口编程(UART0)之中断方式（二）_怀想天空2010的博客-程序员秘密

三．        中断方式的串口编程1.用中断方式编写串口程序由那几部分组成2.硬件上的支持1>UART0 发送FIFO缓冲区A．        UART0含有1个16字节的发送FIFO缓冲区B．        U0THR是UART0发送FIFO的最高字节C．        UART的发送FIFO是一直使能的2>UART0接

Java命令简易入门-2：javac与java命令之一(javac)_zhrb的博客-程序员秘密

Java命令简易入门2-Javac与Java命令（未完待续）文章目录Java命令简易入门2-Javac与Java命令（未完待续）基本概念实验环境与实验文件1.javac与java基本用法2. javac的其他常用参数3. 一个文件中包含多个类文件进行编译4. 类路径参数：-cp或-classpath几个结论参考资料基本概念javac与java命令是我们最常用的Java命令。javac：Java编译器。负责编译，将.java这个文本文件编译成.class字节码文件。java：Java程序启动器。负责

vue使用vant组件时无法修改默认样式问题__Hoodie的博客-程序员秘密

由于vue开发时会在style加上scoped避免全局污染，所以正常开发时直接修改外部组件（vant）的样式时会不生效，我们把scoped删除后会发现样式是可以生效的。但是scoped是肯定不能不要的。所以我们可以用 /deep/（深度监听）来修改样式 /deep/.van-dropdown-menu__title{ font-size: 0.26rem;...

推荐文章

热门文章

相关标签