A C# solution using bit manipulation and hashtable


  • 0
    J
    public class Solution {
    public IList<string> FindRepeatedDnaSequences(string s) {
        List<string> list=new List<string>();
        if(s==null || s.Length<=10) { return list; }
        int hash=0; Dictionary<int, bool> dict=new Dictionary<int, bool>();
        for(int i=0; i<=9; i++)
        { hash=(hash<<2)|GetValue(s[i]); }
        dict[hash]=false; int n=s.Length; int mask=(1<<18)-1;
        for(int i=1; i<=n-10; i++)
        {
            hash=((hash&mask)<<2)|GetValue(s[i+9]);
            if(dict.ContainsKey(hash))
            {
                if(!dict[hash]) {list.Add(s.Substring(i,10)); dict[hash]=true; }
            }
            else
            { dict[hash]=false; }
        }
        
        return list;
    }
    
    private int GetValue(char c)
    {
        if(c=='A') { return 0; }
        else if(c=='C') { return 1; }
        else if(c=='G') { return 2; }
        else { return 3; }
    } }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.