code challenge: count of substring

February 28, 2016

Problem statement

Problems solved in the progression of coding:
1. Runtime error - exceed time limit
   naive solution - compare each substring if it contains 00 or 11
2. Console.ReadLine only reads up to 256 chars, the input is up to 100000 chars.
3. Recursive calls - stack overflow - string length is up to 100000
4. Using iterative solution to replace recursive solution

First, wrote a solution in 20 minutes, but Time exceeding limit - TLE error.
Solution 1: C# code


Solution 2: C# code

So, write second version using recursive to avoid redundant calculation: stack overflow problem

Solution 3: C# code

Then, wrote third version with iterative solution:

Solution 4: C# code
(HackerRank embedded C# executable - wrong answer, but Visual express is ok! Cannot figure out! )


Spent more than 4 hours on this easy question. Totally invest 3 hours nonstop on Sunday afternoon on this problem solving.

What we say to encourage this behavior - have guts to fail. This is just the practice.

March 7, 2017

Need to review last practice and find out a solution.

String functions review

August 23, 2015

1. stringDemo.cpp

Including

atoi 5 versions of implementation

https://github.com/jianminchen/stringDemo/blob/master/Program.cs

2. Scramble string:

https://github.com/jianminchen/scramble-string

3. strstr

Boyer-Moore algorithm

https://github.com/jianminchen/stringDemo/blob/master/Program.cs

Read the string function website and get ideas:

http://www-igm.univ-mlv.fr/~lecroq/string/

http://algs4.cs.princeton.edu/53substring/

http://zjalgorithm.blogspot.ca/2014/12/leetcode-in-java-implement-strstr.html

Need a test case to help me figure out Boyer-Moore algorithm again on August 23, 2015.
Here is a short one for me to memorize the idea:
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/StringMatch/boyerMoore.htm

read the article quickly in 20 minutes on August 23, 2015
http://web.cs.ucdavis.edu/~gusfield/cs224f11/bnotes.pdf

Dec. 12, 2015 video watch:
https://www.youtube.com/watch?v=fHNmRkzxHWs
one of examples the presenter gave in his Cpp conference video.
Know that there is a definitely better algorithm than O(n^2), but also, need to know what the ideas are to beat the naive solution. 

Dec. 11, 2015
Need to work on a small test case, therefore, the algorithm can be easily recalled, and ideas of algorithms can be demoed clearly in the example. Go to find my favorite string, substring. (January 5, 2015, read the wiki page, https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm, read 'The bad character rule' and 'The good suffix rule' )

4. longest palindromic string

5. Look up standard string function implementation, quick review and learn:

January 5, 2016
Read the Java code on the following website:
http://algs4.cs.princeton.edu/53substring/BoyerMoore.java.html

Write a C# version, and check in github, and see if it will help to memorize the algorithm. 

Read the webpage: (well written! now Julia knows two rules: bad character rule, the good suffix rule)
https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

http://www.cs.tufts.edu/comp/150GEN/classpages/BoyerMoore.html