C# primes based O(n) solution


  • 0
    D

    We will have to use the BigInteger class for this, but no issues it's supported in .NetCore 1.1
    Basically, hash strings in prime factorization format .. and divide by s[i] then multiply by s[i+p] to update the new hash .. whenever the hash of s[i..i+p] == hash of p .. then we got a match .. add it ..

    public class Solution {
        private int[] primes = new int[] { 2, 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 };
        
            public IList<int> FindAnagrams(string s, string p)
            {
                IList<int> ret = new List<int>();
                if (s.Length < p.Length) return ret;
    
                BigInteger h = hash(s.Substring(0, p.Length));
                BigInteger hp = hash(p);
                for (int i = 0; i <= (s.Length - p.Length); i++)
                {
                    if (h == hp)
                    {
                        ret.Add(i);
                    }
    
                    h /= (UInt64)primes[s[i] - 'a'];
                    h *= ((i + p.Length) < s.Length) ? (UInt64)primes[s[i + p.Length] - 'a'] : 1;
                }
    
                return ret;
            }
    
            private BigInteger hash(string str)
            {
                BigInteger h = 1;
                foreach (char c in str)
                {
                    h *= (UInt64)primes[c - 'a'];
                }
    
                return h;
            }
    }
    

Log in to reply
 

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