Advertisement
Guest User

Grokking Newsletter 241

a guest
Nov 17th, 2022
42
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.05 KB | Source Code | 0 0
  1. class Solution {
  2. public List<String> findRepeatedDnaSequences(String s) {
  3. if (s.length() < 10) {
  4. return new ArrayList<>();
  5. }
  6.  
  7. final Map<Character, Integer> mask = new HashMap<>();
  8. mask.put('A', 0);
  9. mask.put('C', 1);
  10. mask.put('G', 2);
  11. mask.put('T', 3);
  12.  
  13. int hash = 0;
  14. int windowLen = 10;
  15. int base = 4;
  16. int basePow = (int) Math.pow(base, windowLen - 1);
  17. Set<String> result = new HashSet<>();
  18. Set<Integer> seen = new HashSet<>();
  19.  
  20. for (int i = 0; i < windowLen; i++) {
  21. hash = hash * base + mask.get(s.charAt(i));
  22. }
  23. seen.add(hash);
  24.  
  25. for (int i = 1; i <= s.length() - windowLen; i++) {
  26. hash -= basePow * mask.get(s.charAt(i - 1));
  27. hash = hash * base + mask.get(s.charAt(i + windowLen - 1));
  28.  
  29. if (!seen.add(hash)) {
  30. result.add(s.substring(i, i + windowLen));
  31. }
  32. }
  33.  
  34. return new ArrayList<>(result);
  35. }
  36. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement