using System;
using System.Collections.Generic;
using System.Text;
namespace MSC
{
class Program
{
//“bool F(string s, char ch1, char
ch2, int n)”
//The function determines whether
or not there exists an occurrence of
//ch1 and ch2 separated by a
distance of no more than n in the given
//string s, where s is ascii and
user entered (your function needs
//to work on any input.) The
function must be efficient and
//**optimized** for both space and
time. Please state what the
//complexity of your solution is.
//The time complexity of this
solution is O(N), where N is s.length,
//because the function only scan
the string 1 time.
//The space complexity is O(1),
since no additional data structures
//are used, except some local
variables.
static bool F(string s, char ch1,
char ch2, int n)
{
if (string.IsNullOrEmpty(s) ||
n < 1)
return false;
if (ch1 == ch2)
{
int iLeft = s.IndexOf(ch1);
if (-1 == iLeft)
{
return false;
}
int iRight = s.IndexOf(ch1,
iLeft + 1);
while (-1 != iRight)
{
if (iRight - iLeft <=
n)
{
return true;
}
else
{
iLeft = iRight;
iRight =
s.IndexOf(ch1, iLeft + 1);
}
}//while
}//if
else
{
int iLeft = int.MaxValue;
char chLeft = '\0';
int i = 0;
for (; i < s.Length; ++i)
{
if (s[i] == ch1 || s[i]
== ch2)
{
iLeft = i;
chLeft = s[i];
break;
}
}
++i;
for (; i < s.Length; ++i)
{
if (s[i] == ch1 || s[i]
== ch2)
{
if (chLeft == s[i])
{
iLeft = i;
}
else
{
if (i - iLeft
<= n)
{
return
true;
}
iLeft = i;
chLeft = s[i];
}
}//if
}//for
}//else
return false;
}//end
static void Main(string[] args)
{
Console.WriteLine(F("abcdefg",
'b', 'd', 2));
Console.WriteLine(F("abcdefg",
'b', 'd', 20));
Console.WriteLine(F("abcdefg",
'b', 'e', 1));
Console.WriteLine();
Console.WriteLine(F("abcdefg",
'a', 'b', 0));
Console.WriteLine(F("acbabcd",
'a', 'b', 1));
Console.WriteLine(F("abcdefg",
'x', 'y', 20));
Console.WriteLine(F("abcdefg",
'\0', 'e', 20));
Console.WriteLine(F("abc\0defg", '\0', 'e',
2));
Console.WriteLine();
Console.WriteLine(F("abcdefga",
'g', 'g', int.MaxValue));
Console.WriteLine(F("abcdefga",
'z', 'z', 20));
Console.WriteLine(F("abcdefga",
'a', 'a', 7));
Console.WriteLine(F("abcdefgaa", 'a', 'a',
1));
Console.WriteLine();
Console.WriteLine(F("a", 'a',
'a', 20));
Console.WriteLine(F("a", 'a',
'b', 20));
Console.WriteLine(F("abccccccdefga", 'c',
'e', 2));
Console.WriteLine(F("abccccccdefga", 'c',
'e', 1));
Console.WriteLine(F("abcdefg",
'a', 'g', int.MinValue));
Console.WriteLine();
Console.WriteLine(F("a牛cdefg",
'牛', 'd', 2));
Console.WriteLine(F("a牛马defg",
'牛', '马', 1));
Console.WriteLine(F("a马啊马
defg", '马', '马', 2));
Console.WriteLine(F("a马啊马
defg", '马', '马', 1));
}
}
}
