算法:回溯法(backtracking)解决寻找给定字符串的所有排序(permutations)问题_使用backtracking递归,在permutations.py里实现排列算法,即给定一个字符串,-程序员宅基地

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

字符串的所有排序

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

具体的操作为:

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

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

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

/**
 * @param {string} s
 */
var permutations = function(
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_35714301/article/details/113503468

智能推荐

SQL中按分隔符拆分字符串_sql 分割字符串-程序员宅基地

文章浏览阅读1.8w次,点赞8次,收藏35次。Oracle与hive数据库按分隔符拆分字符串_sql 分割字符串

关于何种情况下使用DataGrid、DataList或Repeater的一些讨论(1) ambushaa [翻译] [转] _datarepeater tabindex<1-程序员宅基地

文章浏览阅读817次。作者:Scott Mitchell[概述]  WEB开发自从有了基于脚本的WEB编程技术(如ASP)以来,经历了一个漫长的过程。通过使用微软的ASP.Net技术,传统的ASP中大量的、单调乏味的、重复性的编程工作成为了历史。例如,象大多数ASP程序员所知的,在ASP中显示数据库内容所需要的过程:  建立数据库连接  用SQL查询装载ADO数据集  显示所需要的任何HTML代码  遍历数据集中的记录_datarepeater tabindex<1

java读取arcgis的gdb文件_java解析gdb文件-程序员宅基地

文章浏览阅读1.5k次。https://blog.wowtools.org/2020/11/05/2020-11-5-java-read-gdb/本文介绍了一种通过java、gdal去读取arcgis gdb文件的方法_java解析gdb文件

Cadence 绘制自己的元器件Part库(填充/实心部分)_cadence原理图封装库怎么填充颜色-程序员宅基地

文章浏览阅读1.6w次,点赞8次,收藏63次。概述 Cadence,使用“OrCAD Capture CIS”组件,绘制自己的原理图元件库,绘制实心Part,步骤。一、新建工程1、双击“Capture CIS 17.4”打开它,如下所示:_cadence原理图封装库怎么填充颜色

Python爬虫——小白笔记(一)_尚硅谷python爬虫笔记-程序员宅基地

文章浏览阅读514次。了解爬虫是什么,做什么_尚硅谷python爬虫笔记

在配置Shiro时,启动tomcat报错出现异常(org.springframework.beans.factory.BeanCreationException)_cannot resolve reference to bean 'securitymanager'-程序员宅基地

文章浏览阅读9k次。今天在配置完shiro后,启动服务器出现了一个问题(org.springframework.beans.factory.BeanCreationException),我觉得可能我们都很容易就会碰到的一个问题。 org.springframework.beans.factory.BeanCreationException: Error creating bea_cannot resolve reference to bean 'securitymanager' while setting bean proper

随便推点

计算机等级考试一级ps内容,计算机等级考试《一级ps》备考练习及答案-程序员宅基地

文章浏览阅读224次。计算机等级考试《一级ps》备考练习及答案10.使用海绵工具可以改变图像的()选择A颜色选择B亮度选择C明度选择D饱和度答案D11.怎样将背景层转换为普通层()选择A双击背景层选择B“图层/栅格化图层”选择C合并到其他图层选择D拼合图层答案A12.在PhotoshopCS中允许一个图像的显示的最大比例范围是多少()选择A100.00%选择B200.00%选择C600.00%选择D1600.00%答案..._计算机一级ps考试内容

07 Object类,Scanner,Arrays类,String类,StringBuffer类,包装类-程序员宅基地

文章浏览阅读85次。Object类的概述:* A:Object类概述 * 类层次结构的根类 * 所有类都直接或者间接的继承自该类* B:构造方法 * public Object() * 子类的构造方法默认访问的是父类的无参构造方法Object类的hashCode()方法 * public int hashCode() * a:返回该对象的哈希码值。默认情况下,该方法会根据..._object string array 层次结构

VSCode用Code Runner编译运行c/c++_code runner c++-程序员宅基地

文章浏览阅读2.9w次,点赞11次,收藏62次。VSCode用CodeRunner快速编译运行首先vscode需要在文件夹下打开,以下所有的文件都需要放到你编写程序文件夹下的.vscode文件夹里平时可以右击文件夹,选择open with code,结构应该是这样的配置CodeRunner下载左下角齿轮找到设置在扩展中找到Run Code configuration,点击在settings.json中编辑加入以下代码,第一..._code runner c++

简单高效,分享几款我在使用的效率神器_火柴共享-程序员宅基地

文章浏览阅读3k次,点赞19次,收藏110次。做一个积极的人编码、改bug、提升自己我有一个乐园,面向编程,春暖花开!今天周六了,分享几款我目前在用的小工具,希望对你有用。使用工具的好处等等,我就不过多介绍了,下面文章的内容是先简单介绍这几款工具,然后说明一下我是怎么应用的。简单的一个思维导图,看下本文全貌:文章目录神器介绍1、火柴-效率神器2、ALTRun - 快速启动3、Typora - Markdown 编辑器4、Snip..._火柴共享

Memory中的Channel/Rank/Bank解析_sram bank-程序员宅基地

文章浏览阅读5.1w次,点赞29次,收藏144次。Memory中的Channel/Bank/Rank解析最近在看网卡底层驱动的一些资料,被内存bank,rank,channel这些关于memory的名词搞得绕来绕去,网上查了一些资料,说得也不全面。在这里让我们一步一步来拆解memory的神秘面纱,从架构到读写逐步解开这块秘密。发挥性memory分两种,SRAM与DRAMRAM(Random Access Memory)随机存取内存,之所以叫做“随机_sram bank

iOS开发笔记之六十六——基于Json的页面动态化方案_ios json 动态化-程序员宅基地

文章浏览阅读1.3w次。******阅读完此文,大概需要15分钟******一、需求场景iOS的动态化一直是工程师们不断致力的方向,尽管JSPatch等动态化方案被苹果否掉之后,类似阿里Weex、点评Picasso这种方案开始成为动态化的另一个重要方向,它们都是通过在App端实现一套JS的引擎,解析js生成Native页面的原理方式,从而达到页面动态化的目的,如果需要复杂的交互App端还需要依赖jscore,基本..._ios json 动态化

推荐文章

热门文章

相关标签