python判断两个字符是否为变位词_Python算法题之“变位词”判断问题

2023-12-07 07:10

本文主要是介绍python判断两个字符是否为变位词_Python算法题之“变位词”判断问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

[TOC]

“变位词”判断问题

问题描述

所谓“变位词”是指两个词之间存在组成字母的重新排列关系

如:heart和earth,Python和typhon

为简单起见,假设参与判断的两个词仅由小写字母构成,而且长度相等

解题目标

写一个bool函数,以两个词作为参数,返回这两个词是否是变位词

解法一:逐字检查

解法思路

将词1中的字符逐个到词2中检查是否存在,存在就”打勾“标记(防止重复)

如果每个字符都能找到,那么这2个词就是变位词,只要有一个字符没有找到,就不是变位词

程序技巧

实现”打勾“标记:将词2对应字符设为None

由于字符串是不可变类型,需要先复制到列表中

10fb876454b34e545d6b6726e3e8d183.png

代码

def abc(s1,s2):

s2_list=list(s2) # str转换为list

pos1=0

stillok = True

while pos1

pos2=0

found = False

while pos2

if s1[pos1]==s2_list[pos2]:

found=True

else:

pos2=pos2+1

if found:

s2_list[pos2] = None

else:

stillok=False

pos1 = pos1+1

return stillok

if __name__ == "__main__":

zzz = abc("abcd","dcba")

print(zzz)

解法二:排序比较

解题思路

将2个字符串先排序

对比是否相等

程序技巧

str转list

进行排序

list转str

进行比较

def Method2(s1,s2):

# 字符串是不可变的无法排序,str转list

list1=list(s1)

list2=list(s2)

# 进行排序

list1.sort()

list2.sort()

# list 转 str

a = ''.join(list1)

b = ''.join(list2)

# 进行比较

if a==b:

return True

else:

return False

if __name__ == "__main__":

zzz2 = Method2('ablc','lcab')

print(zzz2)

解法三:暴力法

解题思路

就是穷尽所有可能的组合

然后将s1中出现的字符进行全排序,再查看s2是否出现在全排列的列表中

这里就不附代码了,暴力法在这里恐怕不是一个好的算法

解法四:计数比较

解题思路

对比两个词中每个字符出现的次数,如果26个字母出现的次数都相同的话,那么这2个就是变位词

程序技巧

def Method4(s1,s2):

c1 = [0]* 26

c2 = [0]* 26

for i in range(len(s1)):

pos = ord(s1[i])-ord('a')

c1[pos] = c1[pos]+1

for i in range(len(s2)):

pos = ord(s2[i])-ord('a')

c2[pos] = c2[pos]+1

stillok =True

j=0

while stillok and j<26:

if c1[j]!=c2[j]:

stillok=False

j+=1

return stillok

if __name__ == "__main__":

zzz4 = Method4('ablc','lcab')

print(zzz4)

这个是四个解法中,性能最优的,T(n)=2n+26

这个解法中依赖额是2个长度为26的计数器列表,来保存字符计数,所以相对于之前3个算法来说,就需要了更多的空间,这里就是用空间换取了时间

这篇关于python判断两个字符是否为变位词_Python算法题之“变位词”判断问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:https://blog.csdn.net/weixin_30185907/article/details/113507753
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/464956

相关文章

Python实现批量提取BLF文件时间戳

《Python实现批量提取BLF文件时间戳》BLF(BinaryLoggingFormat)作为Vector公司推出的CAN总线数据记录格式,被广泛用于存储车辆通信数据,本文将使用Python轻松提取... 目录一、为什么需要批量处理 BLF 文件二、核心代码解析:从文件遍历到数据导出1. 环境准备与依赖库

Python Web框架Flask、Streamlit、FastAPI示例详解

《PythonWeb框架Flask、Streamlit、FastAPI示例详解》本文对比分析了Flask、Streamlit和FastAPI三大PythonWeb框架:Flask轻量灵活适合传统应用... 目录概述Flask详解Flask简介安装和基础配置核心概念路由和视图模板系统数据库集成实际示例Stre

Python实现PDF按页分割的技术指南

《Python实现PDF按页分割的技术指南》PDF文件处理是日常工作中的常见需求,特别是当我们需要将大型PDF文档拆分为多个部分时,下面我们就来看看如何使用Python创建一个灵活的PDF分割工具吧... 目录需求分析技术方案工具选择安装依赖完整代码实现使用说明基本用法示例命令输出示例技术亮点实际应用场景扩

SpringBoot 异常处理/自定义格式校验的问题实例详解

《SpringBoot异常处理/自定义格式校验的问题实例详解》文章探讨SpringBoot中自定义注解校验问题,区分参数级与类级约束触发的异常类型,建议通过@RestControllerAdvice... 目录1. 问题简要描述2. 异常触发1) 参数级别约束2) 类级别约束3. 异常处理1) 字段级别约束

Spring Boot配置和使用两个数据源的实现步骤

《SpringBoot配置和使用两个数据源的实现步骤》本文详解SpringBoot配置双数据源方法,包含配置文件设置、Bean创建、事务管理器配置及@Qualifier注解使用,强调主数据源标记、代... 目录Spring Boot配置和使用两个数据源技术背景实现步骤1. 配置数据源信息2. 创建数据源Be

Python错误AttributeError: 'NoneType' object has no attribute问题的彻底解决方法

《Python错误AttributeError:NoneTypeobjecthasnoattribute问题的彻底解决方法》在Python项目开发和调试过程中,经常会碰到这样一个异常信息... 目录问题背景与概述错误解读:AttributeError: 'NoneType' object has no at

Python使用openpyxl读取Excel的操作详解

《Python使用openpyxl读取Excel的操作详解》本文介绍了使用Python的openpyxl库进行Excel文件的创建、读写、数据操作、工作簿与工作表管理,包括创建工作簿、加载工作簿、操作... 目录1 概述1.1 图示1.2 安装第三方库2 工作簿 workbook2.1 创建:Workboo

基于Python实现简易视频剪辑工具

《基于Python实现简易视频剪辑工具》这篇文章主要为大家详细介绍了如何用Python打造一个功能完备的简易视频剪辑工具,包括视频文件导入与格式转换,基础剪辑操作,音频处理等功能,感兴趣的小伙伴可以了... 目录一、技术选型与环境搭建二、核心功能模块实现1. 视频基础操作2. 音频处理3. 特效与转场三、高

Python实现中文文本处理与分析程序的示例详解

《Python实现中文文本处理与分析程序的示例详解》在当今信息爆炸的时代,文本数据的处理与分析成为了数据科学领域的重要课题,本文将使用Python开发一款基于Python的中文文本处理与分析程序,希望... 目录一、程序概述二、主要功能解析2.1 文件操作2.2 基础分析2.3 高级分析2.4 可视化2.5

一文解密Python进行监控进程的黑科技

《一文解密Python进行监控进程的黑科技》在计算机系统管理和应用性能优化中,监控进程的CPU、内存和IO使用率是非常重要的任务,下面我们就来讲讲如何Python写一个简单使用的监控进程的工具吧... 目录准备工作监控CPU使用率监控内存使用率监控IO使用率小工具代码整合在计算机系统管理和应用性能优化中,监