首页 > 代码库 > leetcode438

leetcode438

public class Solution
    {
        Dictionary<char, int> Dicp = new Dictionary<char, int>();

        Dictionary<char, int> dic = new Dictionary<char, int>();

        string temp = "";

        int curlen = 1;

        int nextindex = 0;

        /// <summary>
        /// 判断第二个字符串是否是第一个字符串的anagram
        /// </summary>
        /// <param name="s1"></param>
        /// <param name="s2"></param>
        /// <returns></returns>
        private bool Judge(string s1, string s2)
        {
            dic.Clear();
            foreach (var c in s1)
            {
                if (!dic.ContainsKey(c))
                {
                    dic.Add(c, 1);
                }
                else
                {
                    dic[c]++;
                }
            }

            foreach (var d in dic)
            {
                if (!Dicp.ContainsKey(d.Key))
                {
                    var st = temp.Substring(0, curlen).LastIndexOf(d.Key);
                    if (st > 0)
                    {
                        nextindex = st;
                    }
                    return false;
                }
            }

            foreach (var d in dic)
            {
                if (d.Value != Dicp[d.Key])
                {
                    return false;
                }
            }
            return true;
        }

        public IList<int> FindAnagrams(string s, string p)
        {
            //temp = s;
            //foreach (var c in p)
            //{
            //    if (!Dicp.ContainsKey(c))
            //    {
            //        Dicp.Add(c, 1);
            //    }
            //    else
            //    {
            //        Dicp[c]++;
            //    }
            //}
            //var list = new List<int>();
            //var len = p.Length;
            //for (int i = 0; i <= s.Length - len; i = nextindex)
            //{                
            //    curlen = nextindex + len;
            //    //var cur = s.Substring(i, len);
            //    if (Judge(s.Substring(i, len), p))
            //    {
            //        list.Add(i);
            //    }
            //    nextindex++;
            //}
            //return list;

            List<int> list = new List<int>();
            if (s == null || s.Length == 0 || p == null || p.Length == 0) return list;
            int[] hash = new int[256]; //character hash
            //record each character in p to hash
            foreach (char c in p)
            {
                hash[c]++;
            }
            //two points, initialize count to p‘s length
            int left = 0, right = 0, count = p.Length;
            while (right < s.Length)
            {
                //move right everytime, if the character exists in p‘s hash, decrease the count
                //current hash value >= 1 means the character is existing in p
                if (hash[s[right++]]-- >= 1) count--;

                //when the count is down to 0, means we found the right anagram
                //then add window‘s left to result list
                if (count == 0) list.Add(left);

                //if we find the window‘s size equals to p, then we have to move left (narrow the window) to find the new match window
                //++ to reset the hash because we kicked out the left
                //only increase the count if the character is in p
                //the count >= 0 indicate it was original in the hash, cuz it won‘t go below 0
                if (right - left == p.Length && hash[s[left++]]++ >= 0) count++;
            }
            return list;
        }
    }

https://leetcode.com/problems/find-all-anagrams-in-a-string/#/description

leetcode438