Is this optimized or what?


  • 0
    X

    the idea is using seqs[] array index to implicitly store scanned 10 length sequency. The 10 length sequence is converted to the array index, and the calculated index is re-used during the scanning.

     public List<String> findRepeatedDnaSequences(String s) {
        List<String> result = new LinkedList<>();
        if(s.length() < 10 || s == null)
          return result;
        
        char[] sC = s.toCharArray();
        int[] toBin = new int[256];
        toBin['A'] = 0;
        toBin['C'] = 1;
        toBin['G'] = 2;
        toBin['T'] = 3;
    
        int size = (int) Math.pow(4, 10);
        boolean[] seqs = new boolean[size];
        boolean[] saved = new boolean[size];
        int index = 0;
        for(int i = 0; i < 10; i++) {
          index <<= 2;
          index |= toBin[sC[i]];
        }
        seqs[index] = true;
        int mod = size - 1;
        for(int i = 10; i < s.length(); i++) {
          index <<= 2;
          index &= mod;
          index |= toBin[sC[i]];
          if(seqs[index] == true) {
            if(saved[index] == false) {
              result.add(s.substring(i-9, i+1));
              saved[index] = true;
            }        
          } else {
            seqs[index] = true;
          }        
        }
        return result;
      }

Log in to reply
 

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