Data scientists at Amazon are working on a utility for genome sequencing algorithms. The utility finds anagram patterns in pairs of DNA sequence strings.
A pair of DNA strings is special if they can be made anagrams after removing any number of occurrences of at most one character from each DNA string.
Given n pairs of DNA strings, for each pair, determine whether it is special. Return a list of boolean values, one for each pair, where True means the pair is special.
Example
Given n = 1, and strings dna1 = "safddadfs" and dna2 = "famafmss".
The strings are anagrams after removing all occurrences of character 'd' from dna1 and character 'm' from dna2.
Return [True].
Note: It is not required that all instances of a character be removed. For example, given "aab" and "ba", one 'a' can be removed from "aab" to leave "ab".
Function Description
Complete the function getSequence in the editor below.
getSequence has the following parameter(s):
string dna[n][2]: the pairs of DNA sequencesReturns
boolean[n]: true if the pair is special and false otherwiseSample Input For Custom Testing
2
2
abcee acdeedb
sljffsaje sljsjeSample Output
1
0这道题要求判断每一对 DNA 字符串是否能通过“最多从每个字符串中删除一种字符的若干个出现次数”变成异位词。核心做法是统计两个字符串每个字母的出现次数差值：如果某个字母在第一个字符串中多出来、在第二个字符串中少了，那么只能通过删掉第一个字符串中的这种字母来抵消；反之亦然。由于每个字符串最多只能选择一种字符删除，所以最终只需要检查正差分和负差分是否都分别集中在至多一种字母上。实现上可以用长度为 26 的计数数组，时间复杂度为每组 O(L)，适合处理较长字符串。
