Advertisement
rishu110067

Dynamic Prograaming-438. Find All Anagrams in a String

Jan 11th, 2022
1,450
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 1.65 KB | None | 0 0
  1. public class Solution {
  2.     public IList<int> FindAnagrams(string s, string p) {
  3.        
  4.         if(s.Length < p.Length){
  5.             return new List<int>();
  6.         }
  7.        
  8.         var maps1 = new Dictionary<char,int>();
  9.        
  10.         for(int i=0; i<p.Length;i++)
  11.         {
  12.             if(maps1.ContainsKey(p[i]))
  13.             {
  14.                 maps1[p[i]]= maps1[p[i]]+1;
  15.             }
  16.             else {maps1[p[i]]=1;}
  17.         }
  18.        
  19.         var res = new List<int>();
  20.        
  21.         for(int i=0; i<p.Length;i++)
  22.         {
  23.             if(maps1.ContainsKey(s[i]))
  24.             {
  25.                 maps1[s[i]]--;
  26.             }
  27.             else {maps1[s[i]]=-1;}
  28.         }
  29.        
  30.         var all_zero = 1;
  31.         foreach(var n in maps1.Values)
  32.         {
  33.             if(n!=0){
  34.                 all_zero = 0;
  35.             }
  36.         }
  37.         if(all_zero == 1){
  38.             res.Add(0);
  39.         }
  40.        
  41.        
  42.         int k = p.Length;
  43.         for(int i=k; i<s.Length;i++)
  44.         {
  45.             if(maps1.ContainsKey(s[i]))
  46.             {
  47.                 maps1[s[i]]--;
  48.             }
  49.             else {maps1[s[i]]=-1;}
  50.            
  51.             if(maps1.ContainsKey(s[i-k]))
  52.             {
  53.                 maps1[s[i-k]] = maps1[s[i-k]]+1;
  54.             }
  55.             else maps1[s[i-k]] = 1;
  56.            
  57.             all_zero = 1;
  58.             foreach(var n in maps1.Values)
  59.             {
  60.                 if(n!=0){
  61.                     all_zero = 0;
  62.                 }
  63.             }
  64.             if(all_zero == 1){
  65.                 res.Add(i-k+1);
  66.             }
  67.         }
  68.        
  69.         return res;    
  70.        
  71.     }
  72. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement