1: namespace Recursion2
2: { 3: /// <summary>
4: /// Question:
5: /// Check if the string s2 is a substring of strign s1 (when s2 is null or empty then return true)
6: /// You can use only string indexer, string Equals, string length and string Substring.
7: /// Use the following signature: bool IsSubstring(string s1, string s2) and solve in recursion.
8: /// </summary>
9: class Program
10: { 11: /// <summary>
12: /// Test the solution
13: /// </summary>
14: /// <param name="args"></param>
15: static void Main(string[] args)
16: { 17: string[] s1s = new string[] { "aaabbbccc", "abc", "cba", "ddca", null, string.Empty }; 18: string[] s2s = new string[] { "aa", "bb", "cc", "dd", "a", "b", "c", "d", "z", string.Empty, null }; 19:
20: s1s.ToList().ForEach(
21: (s1) =>
22: { 23: s2s.ToList().ForEach(
24: (s2) =>
25: { 26: Console.WriteLine("Ver1: {0} is substring of {1} = {2}", s2 ?? "NULL", s1 ?? "NULL",IsSubstringVer1(s1,s2)); 27: Console.WriteLine("Ver2: {0} is substring of {1} = {2}", s2 ?? "NULL", s1 ?? "NULL", IsSubstringVer2(s1, s2)); 28: }
29: );
30: }
31: );
32:
33: Console.ReadLine();
34: }
35:
36: /// <summary>
37: /// Solution - Ver1
38: /// Con: Put high pressure on the GAC (create a lot of strings during the process)
39: /// Pro: No need to add additional funtions
40: /// </summary>
41: /// <param name="s1">string</param>
42: /// <param name="s2">sub string</param>
43: /// <returns>if s2 is s1's substing</returns>
44: public static bool IsSubstringVer1(string s1, string s2)
45: { 46: if (string.IsNullOrEmpty(s2))
47: return true;
48:
49: if (string.IsNullOrEmpty(s1))
50: return string.IsNullOrEmpty(s2);
51:
52: if (s2.Length == s1.Length)
53: return s2.Equals(s1);
54:
55: if (s2.Length > s1.Length)
56: return false;
57:
58: return IsSubstringVer1(s1.Substring(1), s2) //the first combination is to remove the first char from s1
59: || IsSubstringVer1(s1.Substring(0, s1.Length - 1), s2); //the second combination is to remove the last char from s2
60: }
61:
62: /// <summary>
63: /// Solution Ver2
64: /// Pro: No string allocations
65: /// Con: Extra "bootstraped" function
66: /// </summary>
67: /// <param name="s1"></param>
68: /// <param name="s2"></param>
69: /// <returns></returns>
70: public static bool IsSubstringVer2(string s1, string s2)
71: { 72: if (string.IsNullOrEmpty(s2))
73: return true;
74:
75: if (string.IsNullOrEmpty(s1))
76: return string.IsNullOrEmpty(s2);
77:
78: //bootstrap
79: return IsSubstringVer2(s1,1,0,s2,0);
80: }
81:
82: /// <summary>
83: /// Bootstrapped function
84: /// </summary>
85: /// <param name="s1"></param>
86: /// <param name="fallBackIndex">in case of missmach fallback to index</param>
87: /// <param name="s1Index">process s1 in index...</param>
88: /// <param name="s2"></param>
89: /// <param name="s2Index">process s2 in index...</param>
90: /// <returns></returns>
91: private static bool IsSubstringVer2(string s1, int fallBackIndex, int s1Index, string s2, int s2Index)
92: { 93: if (s2Index >= s2.Length)
94: return true; //if we reached here it means that s2 is substring of s1
95:
96: if (s1Index >= s1.Length)
97: return false; //if we reached here it means that s2 is not substring of s1
98:
99:
100: if (s1[s1Index] == s2[s2Index])
101: //if the current chars are the same proceed to the next
102: return IsSubstringVer2(s1, fallBackIndex, s1Index + 1, s2, s2Index + 1);
103:
104: //fall back and start over
105: return IsSubstringVer2(s1, fallBackIndex + 1, fallBackIndex, s2, 0);
106: }
107: }
108: }