亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

python實(shí)現(xiàn)對(duì)變位詞的判斷方法

 更新時(shí)間:2020年04月05日 07:29:20   作者:best beast  
這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)對(duì)變位詞的判斷方法,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下

Python實(shí)現(xiàn)對(duì)變位詞的判斷,供大家參考,具體內(nèi)容如下

什么是變位詞呢?即兩個(gè)單詞都是由相同的字母組成,而各自的字母順序不同,譬如python和typhon,heart和earth。

變位詞的判斷

既然我們知道了變位詞的定義,那么接下來就是實(shí)現(xiàn)對(duì)兩個(gè)單詞是否是變位詞進(jìn)行判斷了,以下展示變位詞判斷的幾種解法:

1、逐字檢查

將單詞1中的所有字符逐個(gè)到單詞2中檢查是否存在對(duì)應(yīng)字符,存在就標(biāo)記
實(shí)現(xiàn):將詞2中存在的對(duì)應(yīng)字符設(shè)置None,由于字符串是不可變類型,需要先將詞2字符復(fù)制到列表中
時(shí)間復(fù)雜度:O(n^2)

def anagramSolution1(s1,s2):
 alist = list(s2) # 復(fù)制s2
 pos1 = 0
 stillok = True
 while pos1 < len(s1) and stillok: # 循環(huán)s1的所有字符
  pos2 = 0
  found = False  # 初始化標(biāo)識(shí)符
  while pos2 < len(alist) and not found:  # 與s2的字符逐個(gè)對(duì)比
   if s1[pos1] == alist[pos2]:
    found = True
   else:
    pos2 = pos2 + 1
  if found:
   alist[pos2] = None # 找到對(duì)應(yīng),標(biāo)記
  else:
   stillok = False # 沒有找到,失敗
  pos1 = pos1 + 1
 return stillok
print(anagramSolution1('python','typhon'))

2、排序比較

實(shí)現(xiàn):將兩個(gè)字符串都按照字母順序重新排序,再逐個(gè)比較字符是否相同
時(shí)間復(fù)雜度:O(n log n)

def anagramSolution2(s1,s2):
 alist1 = list(s1)
 alist2 = list(s2)

 alist1.sort()   # 對(duì)字符串進(jìn)行順序排序
 alist2.sort()
 pos = 0
 matches = True
 while pos < len(s1) and matches:
  if alist1[pos] == alist2[pos]:  # 逐個(gè)對(duì)比
   pos = pos + 1
  else:
   matches = False
 return matches
print(anagramSolution2('python','typhon'))

3、窮盡法

將s1的字符進(jìn)行全排列,再查看s2中是否有對(duì)應(yīng)的排列
時(shí)間復(fù)雜度為n的階乘,不適合作為解決方案

4、計(jì)數(shù)比較

將兩個(gè)字符串的字符出現(xiàn)的次數(shù)分別統(tǒng)計(jì),進(jìn)行比較,看相應(yīng)字母出現(xiàn)的次數(shù)是否一樣
時(shí)間復(fù)雜度:O(n),從時(shí)間復(fù)雜度角度而言是最優(yōu)解

def anagramSolution4(s1,s2):
 c1 = [0] * 26
 c2 = [0] * 26
 for i in range(len(s1)):
  pos = ord(s1[i]) - ord('a')  # ord函數(shù)返回字符的Unicode編碼,此語句可以將字符串中的字母轉(zhuǎn)換成0-25的數(shù)字
  c1[pos] = c1[pos] + 1  # 實(shí)現(xiàn)計(jì)數(shù)器
 for i in range(len(s2)):
  pos = ord(s2[i]) - ord('a')
  c2[pos] = c2[pos] + 1
 j = 0
 stillOK = True
 while j < 26 and stillOK:   # 計(jì)數(shù)器比較
  if c1[j] == c2[j]:
   j = j + 1
  else:
   stillOK = False
 return stillOK
print(anagramSolution4('python','typhon'))

總結(jié)

從以上幾種解法可以看出,要想在時(shí)間上獲得最優(yōu)就需要犧牲空間存儲(chǔ),因此沒有絕對(duì)的最優(yōu)解,只有在一定的平衡下,才能找到一個(gè)問題相對(duì)穩(wěn)定的解決方案。

以上就是本文的全部內(nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。

相關(guān)文章

  • python requests post多層字典的方法

    python requests post多層字典的方法

    今天小編就為大家分享一篇python requests post多層字典的方法,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
    2018-12-12
  • python連接FTP服務(wù)器的實(shí)現(xiàn)方法

    python連接FTP服務(wù)器的實(shí)現(xiàn)方法

    本文主要介紹了python連接FTP服務(wù)器的實(shí)現(xiàn)方法,主要使用ftp操作進(jìn)行連接FTP服務(wù)器、獲取當(dāng)前目錄文件清單、上傳文件等操作,具有一定的參考價(jià)值,感興趣的可以了解一下
    2022-06-06
  • python掃描proxy并獲取可用代理ip的實(shí)例

    python掃描proxy并獲取可用代理ip的實(shí)例

    下面小編就為大家?guī)硪黄猵ython掃描proxy并獲取可用代理ip的實(shí)例。小編覺得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧
    2017-08-08
  • Python+PyQT5的子線程更新UI界面的實(shí)例

    Python+PyQT5的子線程更新UI界面的實(shí)例

    今天小編就為大家分享一篇Python+PyQT5的子線程更新UI界面的實(shí)例,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
    2019-06-06
  • Python中ConfigParser模塊示例詳解

    Python中ConfigParser模塊示例詳解

    有些時(shí)候在項(xiàng)目中,使用配置文件來配置一些靈活的參數(shù)是比較常見的事,因?yàn)檫@會(huì)使得代碼的維護(hù)變得更方便,而ini配置文件是比較常用的一種,今天介紹用ConfigParser模塊來解析ini配置文件,感興趣的朋友一起看看吧
    2023-01-01
  • 如何使用Python基于接口編程的方法實(shí)現(xiàn)

    如何使用Python基于接口編程的方法實(shí)現(xiàn)

    本文主要介紹了如何使用Python基于接口編程,文中通過示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-11-11
  • Python使用numpy模塊創(chuàng)建數(shù)組操作示例

    Python使用numpy模塊創(chuàng)建數(shù)組操作示例

    這篇文章主要介紹了Python使用numpy模塊創(chuàng)建數(shù)組操作,結(jié)合實(shí)例形式分析了Python使用numpy模塊實(shí)現(xiàn)數(shù)組的創(chuàng)建、賦值、修改、打印等相關(guān)操作技巧與注意事項(xiàng),需要的朋友可以參考下
    2018-06-06
  • pandas讀取CSV文件時(shí)查看修改各列的數(shù)據(jù)類型格式

    pandas讀取CSV文件時(shí)查看修改各列的數(shù)據(jù)類型格式

    這篇文章主要介紹了pandas讀取CSV文件時(shí)查看修改各列的數(shù)據(jù)類型格式,本文給大家介紹的非常詳細(xì),具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2019-07-07
  • 如何使用Python代碼創(chuàng)建表格

    如何使用Python代碼創(chuàng)建表格

    如果能夠?qū)⑽覀兊臒o序數(shù)據(jù)快速組織成更易讀的格式,對(duì)于數(shù)據(jù)分析非常有幫助,下面這篇文章主要介紹了關(guān)于如何使用Python代碼創(chuàng)建表格的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下
    2023-06-06
  • python logging 重復(fù)寫日志問題解決辦法詳解

    python logging 重復(fù)寫日志問題解決辦法詳解

    這篇文章主要介紹了python logging 重復(fù)寫日志問題解決辦法詳解,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-08-08

最新評(píng)論