首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。