Lintcode 1900 · Gene Similarity [Python]

本文主要是介绍Lintcode 1900 · Gene Similarity [Python]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一开始当然是暴力了，结果绝对是MLE了。然后可以这么思考吧，双指针，先把两个串的数字量和字母转化为两对list。然后先对比两个数字，并减去两个数字的较小的数字量，然后判断此时，两个list数字的index对应的字母一样不，一样则说明对位的字母一样，res作为一样位置和字母的统计量，增加两个数字的较小的数字。不一样，则说明对位对比每一个对的上的。然后判断，此时两个数字减去较小数字后，哪一个为0，为0的，则其对应的index向前增加一，指向下段字母开始的位置，和未被减完的前一个字母串的剩下部分开始对比。G家的题目，确实巧妙。。。惹不起。。。

class Solution:"""@param Gene1: a string@param Gene2: a string@return: return the similarity of two gene fragments"""def GeneSimilarity(self, Gene1: str, Gene2: str) -> str:# write your code herenumberslist1, charslist1 = self.transfer(Gene1)numberslist2, charslist2 = self.transfer(Gene2)idx1, idx2 = 0, 0res = 0total = sum(numberslist1)while idx1 < len(numberslist1) and idx2 < len(numberslist2):decrease = min(numberslist1[idx1], numberslist2[idx2])if charslist1[idx1] == charslist2[idx2]:res += decreasenumberslist1[idx1] -= decreaseif numberslist1[idx1] == 0:idx1 += 1numberslist2[idx2] -= decreaseif numberslist2[idx2] == 0:idx2 += 1return str(res) + '/' + str(total)def transfer(self, Gene):numberslist = []charslist = []i = 0while i < len(Gene):thenumber = 0while Gene[i].isdigit():thenumber = thenumber * 10 + int(Gene[i])i += 1numberslist.append(thenumber)charslist.append(Gene[i])i += 1return numberslist, charslist

1900 · Gene Similarity
Algorithms
Hard
Accepted Rate
43%

DescriptionSolutionNotesDiscussLeaderboard
Description
Given two gene fragment Gene1 and Gene2, the gene fragment is composed of numbers and four characters: “ACGT”.
Each character is preceded by a corresponding number, which describes the number of consecutive occurrences of the character. For example, “1A2C2G1T” means “ACCGGT”.
Return a string which denote the similarity of two gene fragments.
The definition of similarity string is that “the number of characters equal in the same position” + “/” + “the total number of characters”.

Gene1 and Gene2 only contain [“A”, “C”, “G”, “T”] and digit.
The length of Gene1 and Gene2 is within range: [1, 100000]
The count of characters is within range: [1, 10000000]
Guarantee the length of Gene1 and Gene2 by expansion are equal.
Example
Example 1:
Input:
Gene1: “2T3G”
Gene2: “3T2G”
Output:
“4/5”
Explanation:
“TTTGG” and “TTGGG” have 4 position same gene, so “4/5”
Example 2:
Input:
Gene1 = “3T2G4A1C”
Gene2 = “6T1A2C1G”
Output:
“4/10”
Explanation:
“TTTGGAAAAC” and “TTTTTTACCG” hava 4 position gene same, so “4/10”