Find if 2 lines are anagram in O (1) space and O (n) time

Question

You can find if 2 lines are anagrams after sorting both lines in O (nlogn) time, however you can find it in o (n) time and O (1) space.

Answer 1

Absolutely no expert here ...

But why not go through each line and just count how many times each letter appears.

With the appropriate implementation, this should not take more time O (n).

Answer 2

[26], , , , , , , . O (n)

Answer 3

, . , .

let h => hash which maps letters to occurence_count (initialized to 0)

for each letter l in string a
  h[l] = h[l] + 1
end

for each letter l in string b
  h[l] = h[l] - 1
end

for each key l in h 
  return false if h[l] != 0
end

return true

O (n) + O (n) + c = O (n). 26- , . , O (26) = O (1)

[[]], , :

let h => hash which maps letters to occurence_count (initialized to 0)

#this loop runs n times
for each letter l in string a
  #hash lookups / writes are constant time
  h[l] = h[l] + 1
end
#above function ran O(n) time

for each letter l in string b
  h[l] = h[l] - 1
end

#runs in O(alphabet) = O(c) = constant-time
for each key l in h 
  return false if h[l] != 0
end

return true

Answer 4

---

.

1 - -
hashCode, :

static int[] primes = {3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103};
static String alphabet = "abcdefghijklmnopqrstuvwxyz";


public static int hashCode(String s){
    int sum = 0;

    for(char c: s.toCharArray()){
      sum += primes[c-97];
    }
    return sum;
}

, hashCode , . , Jin, - hashCode .
- O (n)

2 - hashmap
2 2 . , hashmap char , , . , , hashmap, , . , 0, 2 .

3 - count ( )

 
boolean are_anagrams(string1, string2){
 
    let counts = new int[26];
 
    for each char c in lower_case(string1)
        counts[(int)c]++
 
    for each char c in lower_case(string2)
        counts[(int)c]--
 
    for each int count in counts
        if count != 0
            return false
 
    return true
}

.

Answer 5

. , , ( , ) .

Answer 6

: O(n) + O(n) = O(n)

: O(256) = O(1)

Java

private static boolean isAnagramWithOneArray(String strFirst, String strSecond) {
    int[] charsCount = new int[256];

    if (strFirst != null && strSecond != null) {
        if (strFirst.length() != strSecond.length()) {
            return false;
        }
        for (int i = 0; i < strFirst.length(); i++) {
            charsCount[strFirst.charAt(i)]++;
            charsCount[strSecond.charAt(i)]--;
        }
        for (int i = 0; i < charsCount.length; i++) {
            if (charsCount[i] != 0) {
                return false;
            }
        }
        return true;
    } else {
        return (strFirst == null && strSecond == null);
    }
}

Answer 7

unsigned char CharacterCheck(char item)
{

    if ((item >= 'A') && (item <= 'Z'))
        return (item - 'A');

    if ((item >= 'a') && (item <= 'z'))
        return ((item - ('a' - 'A')) - 'A');

    return -1;

}

unsigned char AnagramCheck6 (char * item1, char * item2)
{
    char *test                      = item1;
    char *test2                     = item2;
    int count                       = 0;
    unsigned char rc                = 0;
    unsigned char rslt              = 0;

    while (*test && *test2)
    {
        rslt = CharacterCheck(*test++);

        if (rslt != 0xff)
            count += rslt;

        rslt = CharacterCheck(*test2++);

        if (rslt != 0xff)
            count -= rslt;
    }

    if (*test)
    {
        while (*test)
        {
            rslt = CharacterCheck(*test++);

            if (rslt != 0xff)
                count += rslt;
        }
    }

    if (*test2)
    {
        while (*test2)
        {
            rslt = CharacterCheck(*test2++);

            if (rslt != 0xff)
                count -= rslt;
        }
    }

    if (count)
        rc = 1;

    return rc;

}

. ,

Answer 8

rateher ,

Answer 9

, . ascii, , , -, . / O (n), . count , , O (m + n) , UTF-32.

, O (n lg n), quicksort , .

Answer 10

-, :

//is s an anagram of t?
#include <string>

bool is_anagram(const string& s, const string& t)
    {
    bool ret = false;

    //if s and t are anagrams, they must of same size
    if( s.length() != t.length() )
        {
        return ret;
        }

        //assume that s and t have valid ascii characters only
    char letters[ 256 ] = {0};
    int i;

    // find occurence of each character in string s
    for( i = 0; i < s.length(); i++ )
        {
        (letters[ s[i] ])++;
        }

    // now, find occurence of each character in string t, but decrement 
    // correspnding character
    for( i = 0; i < t.length(); i++ )
        {
        //if the count is <0 means the given character is not present in s
        if( --(letters[ t[i] ]) < 0 ) 
            {
            return ret;
            }
        }

    //out of for loop means success
    ret = true;
    return ret;
    }

Answer 11

- :

    String str1 = "test";
    String str2 = "tzet";
    int count = 0;
    for (int i = 0; i < str1.length(); i++)
    {
        count = count + str1.charAt(i) - str2.charAt(i);
    }
    System.out.println(count);

2 1 ( ASCII). , .

, .