Help: Is the running time of my program O(n)?


  • 0
    C

    This is my AC solution. When I was computing the total running time, I am not sure what is the running time of some Java built-in functions. Specifically:

    String.charAt(int index); ---is it O(1) or O(n)?

    String.valueOf(int k);

    Collection.addAll(Collection c); ---I think it is O(n) where n is the size of c but did not find any document giving an explanation.

    String1 += String2; ---I googled this and found out some people said it is O(n) where n is the length of string1, since java create a copy of string1 when doing string addition. However, I am not sure if they are right.

    If anyone could give me an answer, or even your thought, I will so much appreciate that. Thanks!

    public class Solution {
        public List<String> anagrams(String[] strs) {
            List<String> result = new ArrayList<>();
            if (strs == null || strs.length == 0) return result;
            Map<String, String> map = new HashMap<>();
            Set<String> set = new HashSet<>();
            for (int i = 0; i < strs.length; i++) {
                if (strs[i].equals("")) {
                    if (map.containsKey("")) {
                        set.add("");
                        result.add("");
                    }
                    else map.put("", "");
                } else {
                    int[] arr = new int[26];
                    String str = "";
                    for (int j = 0; j < strs[i].length(); j++) arr[strs[i].charAt(j) - 'a']++;
                    for (int k = 0; k < 26; k++) str += String.valueOf(arr[k]);
                    if (map.containsKey(str)) {
                        set.add(map.get(str));
                        result.add(strs[i]);
                    } else map.put(str, strs[i]);
                }
            }
            result.addAll(set);
            return result;
        }
    }

  • 1
    S

    Your algorithm runs in O(NM) where M is the average length of the string. You are correct that String concatenation takes linear time of string length, but that doesn't matter because you only concatenate constant number of times, so the complexity for that step is still O(1).


  • 0
    C

    It makes much sense. Thanks!


Log in to reply
 

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