Java 28ms Solution Beats 100% of Java Submissions


  • 11
    X

    The idea is inspired by @crazyirontoiletpaper's solution.

    public class Solution {
        public List<String> findRepeatedDnaSequences(String DNA) {
            ArrayList<String> res = new ArrayList<String>();
            if(DNA.length()<10)    return res;
            HashSet<Integer> once = new HashSet<Integer>();
            HashSet<Integer> twice = new HashSet<Integer>();
            int[] map = new int[26];
            map['A'-'A'] = 0;
            map['C'-'A'] = 1;
            map['G'-'A'] = 2;
            map['T'-'A'] = 3;
            int enc = 0;
            for(int i=0; i<9; ++i){
                enc <<=2;
                enc |= map[DNA.charAt(i)-'A'];
            }
            for(int j=9; j<DNA.length(); ++j){
                enc <<=2;
                enc &= 0xfffff;
                enc |= map[DNA.charAt(j)-'A'];
                if(!once.add(enc) && twice.add(enc))
                    res.add(DNA.substring(j-9,j+1));
            }
            return res;
        }
    }

  • 0
    I

    A C# port of it could beat only 80% of the submissions:

    public class Solution {
        public IList<string> FindRepeatedDnaSequences(string s) {
            var list = new List<string>();
            if(s.Length<10){return list;}
            HashSet<int> once=new HashSet<int>();
            HashSet<int> twice=new HashSet<int>();
            var arr=new int[26];
            arr['A'-'A']=0;
            arr['C'-'A']=1;
            arr['G'-'A']=2;
            arr['T'-'A']=3;
            int enc = 0;
            for(int i=0; i<9; ++i){
                enc <<=2;
                enc |= arr[s[i]-'A'];
            }
            for(int j=9; j<s.Length; ++j){
                enc <<=2;
                enc &= 0xfffff;
                enc |= arr[s[j]-'A'];
                if(!once.Add(enc) && twice.Add(enc))
                    list.Add(s.Substring(j-9,10));
            }
            return list;
        
        }
    }

  • 0
    P

    why this --> enc &= 0xfffff;
    why map of size 26


Log in to reply
 

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