Repeated DNA Sequences

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].

解题思路：

1、用map存储已经扫描过的子串，并对之计数。时间复杂度为O(n)。代码如下：

class Solution {
public:
    vector findRepeatedDnaSequences(string s) {
        map count;
        
        vector result;
        
        int len = s.length();
        for(int i=0; i::iterator it=count.find(str);
            if(it!=count.end()){
                count[str]=1;
            }else{
                if(it->second==1){
                    result.push_back(str);
                }
                count[str]++;
            }
        }
        
        return result;
    }
};

但是会报内存溢出错误。

2、为AGCT分别编码，共有4种，故只需两位便能编码。共十个字符，只需20位就能表示任何一种组合。int类型32位，因此可以用一个int类型来存储10个字符串。每检查一个字符之后，需要将最高位置为0。代码如下：

class Solution {
public:
    vector findRepeatedDnaSequences(string s) {
        const int subStrLen = 10;
        const int mask = 0x3ffff;
        
        map count;
        
        map cCode;
        cCode['A']=0;
        cCode['C']=1;
        cCode['G']=2;
        cCode['T']=3;
        
        vector result;
        
        int len = s.length();
        
        int code=0;
        
        if(len>subStrLen){
            string str = s.substr(0, subStrLen);
            for(int i=0; i

 
转载请注明： » [LeetCode] Repeated DNA Sequences

<!--
                    

                    	

                        	

                            	
                            
                        
                        

                        	

                            	
相关博文：
                                

                                	
                                    	
                                        	
                                        
                                        
定制桌面成功案例
                                    
                                    
                                    	
                                        	
                                        
                                        
海量文档查同或聚类问题 -- Locality Sensitive Hash 算法 （转）
                                    
                                    
                                    	
                                        	
                                        
                                        
汉字转拼音c/c++源码，支持gb2312和utf8
                                    
                                    
                                    	
                                        	
                                        
                                        
数据库顶级会议——SIGMOD介绍
                                    
                                
                            
                        
                    
                    -->