O(n) time and O(n) space complexity in Java


  • 0
    J

    public class Solution {

        public List<String> findRepeatedDnaSequences(String s) {
            LinkedList<String> result = new LinkedList<String>();
            LinkedList<String> map = new LinkedList<String>();
            for(int i=0; i<s.length()-9;i++){
                String sub = s.substring(i, i+10);
                if(map.contains(sub)){
                    result.add(sub);
                }else{
                    map.add(sub);
                }
            }
            return result;
        }
    

    }


  • 0

    LinkedList.contains is of course linear, making your code O(n**^2**), not O(n). And since there is a test case with very many different substrings, your code has no change to get accepted.


Log in to reply
 

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