首页 > 代码库 > Common Child

Common Child

题目如下:

技术分享

Sample Input #0

HARRYSALLY

Sample Output #0

2

The longest possible subset of characters that is possible by deleting zero or more characters from HARRY andSALLY is AY, whose length is 2.

Sample Input #1

AABB

Sample Output #1

0

AA and BB has no characters in common and hence the output is 0.

Sample Input #2

SHINCHANNOHARAAA

Sample Output #2

3

The largest set of characters, in order, between SHINCHAN and NOHARAAA is NHA.

Sample Input #3

ABCDEFFBDAMN

Sample Output #3

2

BD is the longest child of these strings.

 另外一些测试用例:

  • WEWOUCUIDGCGTRMEZEPXZFEJWISRSBBSYXAYDFEJJDLEBVHHKS FDAGCXGKCTKWNECHMRXZWMLRYUCOCZHJRRJBOAJOQJZZVUYXIC
  • 结果:15
  • ELGGYJWKTDHLXJRBJLRYEJWVSUFZKYHOIKBGTVUTTOCGMLEXWDSXEBKRZTQUVCJNGKKRMUUBACVOEQKBFFYBUQEMYNENKYYGUZSPFRVIFOVJYQLVZMFBNRUTIYFBMFFFRZVBYINXLDDSVMPWSQGJZYTKMZIPEGMVOUQBKYEWEYVOLSHCMHPAZYTENRNONTJWDANAMFRX
  • 结果:27
  • APMCTKBUKYRGZPAUVZEBVUXRGDVITOYXWQWRVCSXESMEHQLHPDJQWETAWQVSBRRNRRFDLFTRXOTKQHFTYAZSGBORDNAMUAJTPVOKERLVOLEALDQQLUDCU
IRXJHQEZBRWYPFJXNTPELEZHNJILIZVZLYQJDFYSYQNRFFAOYXHQBQVRLFDIIOGWKQIZGVELYOUKZBKMHVYGIKIPSEMWSCWYOJTHOQKMLBAIZYNAKYNCXKDTTES
ODDAEAHKCDHCJYAHERACMLYQHXIRDFUSRTZDNVHSYFKCSPPYSLHOGIBTNUJTZQWVTHKUNDNWZADMATSUXEISCACQNQXIHNTXGCZUGIGBDONYTUXAXFINAYGZJVD
CTZCWPGFNQDPERUCNJUXIFDSQHULYPZRNUOKMLMMQAJMLKCHJMEFJVRYZIPFQOBSDPAITHGMNKROCWJEGESCGOIUOQ
HOYUEQNPJPBMCNRZUHOSQNSUNCSTVQVWFGMUFJZGMEUVUPH
  • JUVSDRRSHFGSSLLLZEPJDVAWDPKQBKUHHOZFFXKQMGAACZUYOMNPHWGTYZWQGSMNYXWNFYNOIVVMPZXUNKJQYBYJINBOHXUWIVRTVLEKCOPDMTKTGDBWE
CDAVPMLHQLERZHDVZJZODPSAPGSRWJXNGFEBQBLTLNDIEGFHEGHJWFOIYXRUJMODSNXUFWBIJJMXTFMUKQEYPNBTZFEJNLDNWCGQLVUQUKGZHJOKZNPMUYEQLE
YNNORKJQAMSTHTBCCPQTTCPRZATWNJQJXPODRXKIWDOFUBZVSDTAPFRMXJBJMUGVRZOCDUIPXVEGMRQNKXDKNWXMTNDJSETAKVSYMJISAREEJPLRABMXJSRQNA
SOJNEEVAMWCFJBCIOCKMHCMYCRCGYFNZKNALDUNPUSTSWGOYHOSWRHWSMFGZDWSBXWXGVKQPHGINRKMDXEVTNNZTBJPXYNAXLWZSBUMVMJXDIKORHBIBECJNKWJJJSRLYQIKKPXSNUT

结果:155


在hackerrank刷到的题,好难~。

而且关键在于运行效率,我用的方法是递归,题目里给的几个例子还勉强能运行出结果,后面测试的时候完全运行不完。

要好好提高算法!

贴出自己的代码,有一个长一点的串,但是没有运行对。所以也不知道自己的算法的问题是只是效率不行还是逻辑本身就有问题。。

 1 int searchSubStr(string aStr, string bStr,int comLen){ 2  3     int count = 0; 4     int newcount = comLen; 5     int aLen = aStr.length(); 6     int bLen = bStr.length(); 7     for (int i = 0; i < aLen; i++){ 8          9         for (int j = 0; j < bLen; j++){10                 11             if (aStr.at(i) == bStr.at(j)){12                 13                 count =  searchSubStr(aStr.substr(i+1,aLen-i-1),bStr.substr(j+1,bLen-j-1),comLen+1);14 15             }16         }17 18         if (count>newcount){19             newcount = count;20         }21     }22 23     return newcount;24 }

 

Common Child