danyluis
BAN USERHere's another solution using a sliding window.
int[] Histogram(string a, int idx, int length)
{
int buffSize = (int)('z' - 'A' + 1);
int[] hist = new int[buffSize];
for (int i = 0; i < length; i++) hist[a[i + idx] - 'A']++;
return hist;
}
bool SameHist(int[] h1, int[] h2)
{
for (int i = 0; i < h1.Length; i++)
if (h1[i] != h2[i]) return false;
return true;
}
public bool ContainsAnagramSlidingWindow(string a, string str)
{
if (string.IsNullOrEmpty(a)) return true;
if (a.Length > str.Length) return false;
int[] histA = Histogram(a, 0, a.Length); // a's total histogram
int[] histStr = Histogram(str, 0, a.Length); // str's partial histogram
int i = 0;
while (true)
{
// Compare str's partial histogram to a's histogram
if (SameHist(histA, histStr)) return true;
if (i == str.Length - a.Length) break;
// Move window one step ahead
histStr[str[i] - 'A']--;
histStr[str[i + a.Length] - 'A']++;
i++;
}
return false;
}
This solution could be improved this way: instead of sorting each substring (line: "Array.Sort(subArray)") as we move the sliding window through the big string, we can just delete one occurrence of the last character of the substring visited in the previous iteration from the current window's string, and insert-sort the character visited on the current iteration in the current window's string. This small part of the algorithm is only O(M) (M being the length of the anagram string), instead of O(MlogM) which is what it takes to sort it each time. I might publish the code later.
- danyluis April 07, 2014Correct! I would use binary search. Here it goes:
public bool IsPerfectSquare(int n)
{
if (n == 1) return true;
if (n < 4) return false;
int min = 2;
int max = n / 2;
do
{
int div = (max + min) / 2;
int res = n / div;
if (res * res == n) return true;
if (res < div)
{
min = res;
max = div;
}
else
{
min = div;
max = res;
}
} while (max > (min + 1));
return false;
}
My solution:
1- Sort characters of a
2- For each contiguous-character substring S of length == a.Length in b
2.1- Sort the characters of S
2.2- if S == a, return true
3- return false
public bool ContainsAnagram(string a, string b)
{
if (b.Length < a.Length) return false;
char[] aArray = a.ToArray<char>();
Array.Sort(aArray);
a = new string(aArray);
for (int i = 0; i <= b.Length - a.Length; i++)
{
string sub = b.Substring(i, a.Length);
char[] subArray = sub.ToArray<char>();
Array.Sort(subArray);
sub = new string(subArray);
if (string.Compare(sub, a, false) == 0) return true;
}
return false;
}
- Get digits of N in positional order
- Find first digit M that is not in ascending order (searching from right to left)
- If all digits are in ascending order from right to left, then return N
- Find the smallest digit P that is to the right of M and is also larger than M
- Swap positions of M and P
- Sort digits after original position of M in ascending order from left to right
- Build and return from digits
public int NextLargest(int n)
{
byte[] digits = new byte[10];
int length = 0;
while (n > 0)
{
digits[length++] = (byte)(n % 10);
n /= 10;
}
Array.Reverse(digits, 0, length);
int swapPos = -1;
for (int i = length - 2; (i >= 0) && (swapPos == -1); i--)
if (digits[i] < digits[i + 1]) swapPos = i;
if (swapPos == -1) return n;
int swapPos2 = -1;
int min = int.MaxValue;
for (int i = swapPos + 1; i < length; i++)
{
if ((digits[i] > digits[swapPos]) && (digits[i] < min))
{
min = digits[i];
swapPos2 = i;
}
}
byte bTemp = digits[swapPos];
digits[swapPos] = digits[swapPos2];
digits[swapPos2] = bTemp;
Array.Sort(digits, swapPos + 1, length - swapPos - 1);
for (int i = 0; i < length; i++)
n = n * 10 + digits[i];
return n;
}
Repewasam940, Backend Developer at Absolute Softech Ltd
I am a 29-year-old Investment Advisor from New York. I help people make the right investment decision. I met many ...
RepErmanStern, Applications Developer at ADP
I am Erman . I am metal finishing-, plating- and coating-machine operators operate and monitor equipment which finishes, plates and coats ...
Replevijhoyt, Android Engineer at A9
Hello, I am working as a machine operator and we are working in manufacturing units and operate equipment to create ...
RepJanie Margreta, Android Engineer at Achieve Internet
JanieMargreta works as a plant operator, an employee who supervises the operation of an industrial plant. Where I have to ...
Repcassicjohnson, Android Engineer at Accenture
Hi, I work as an Painter, making art Paintings for the world’s top art galleries. When I have an ...
Repileenjconnelly, Cloud Support Associate at Absolute Softech Ltd
I have extensive experience in providing breaking news and giving precise details to the viewers. Interested in leading/working with ...
Repsusiejcrider, Member Technical Staff at Accolite software
I was a Communications Consultant with experience in working across various clients .technology, consumer, hospitality, financial services and corporate social ...
RepFanieGoode, Consultant at Achieve Internet
I am a Media Library Assistant that provides integrated support for two popular “Multi Language/ Multilingual/ Internationalization” plugins; WPML and ...
Repmonicaralvarado94, Korean Air Change Flight at Athena Health
I am fond of reading stories then reading articles which are all about a story of a beautiful nature and ...
Hi: yes! I also thought about doing it with a Dictionary (C#), and I think it would be particularly useful when the alphabet is big. And, also, it wouldn't be more difficult to implement than this solution. Would you be willing to write and post it?
- danyluis April 20, 2014