MS on Friday, a top question

xiaoxiao2021-03-31  181

Topic Requirements: Write a function that returns the maximum common string in two arbitrary strings, that is, the ABCDEF and QCFBCC return values ​​are BC language.

My idea: 1. Determine a string to a long string, another string is short string, find a short string in the long string (the longest commuter possibility in the long string is short string itself) 2. Sequential determination short strings Each character appears in a long string (first make a predetermined bit) 3. Such as satisfying the condition 2, that is, a character in the short string appears in the long string, trying to find a short string from this character in the long string The entire string of the end 4. If the condition 3 is not satisfied, the short strings will be reduced by 1 character until the maximum length (at least one character) appears (at least a character) 5. Compare the character length of this time, compared with the temporary variable If the length is greater than the historical length, the value returns the value of 6. Repeat 2-5 until the end of the string

My implementation: C # version public static string getpubmaxstring (string value1, string value2) {string result = null, stmp; int maxlen = 0; if (value2.Length> Value1.length) // Make sure Value1 is a long string {stmp = Value1; value1 = value2; value2 = stmp;} for (int i = 0; i - 1) // Whether each character of the string occurs {stmp = value2.substring (i); // Intercept the short string appears in the end of the end of the variable for (INT II = stmp.length; II> 0; II -) {IF Value1.indexOf (stmp.substring (0, ii))> - 1) // The left stem of the short string variable appears if the short string variable occurs in sequence, and the length of this string is greater than the upper String length {Result = stmp.substring (0, ii); maxlen = II;}}}}}}}} Return Result;

At that time, I didn't need a pen in half a year. I was very noisy next to it (like another interview in questioning Struts problem), I wanted to overclock in ten minutes. Going home is actually a little wrong, it seems that there is no old. Not used; of course, I believe that there is also a better algorithm to achieve this topic and exchange communication with you, I hope to see everyone's inspirational ideas and algorithms.

I saw SOHOLI (Tianya Lonely) netizen on 9CBS to achieve a more concise algorithm: public static string getLargepublicString (string a, string b) {string shortstring = a.length> B.Length? B: a; // Short; string longstring = a.length> b.length? A: b; // take longer; for (int i = shortstring.length; i> 0; i -) // length Decreme {for (int J = 0; j <= shortstring.length - i; j ) // position increment {if (longstring.indexof (shortstring.substring (j, i))! = -1) {Return Shortstring.Substring (j, i) }}} Return string.empty;} It can be achieved if it is unique and simple, the only disadvantage is that this algorithm is slightly slower than my implementation, especially in two text strings. Under the case, because the two achieve the most core differences are that my getPubmaxString is the first character that does exist first, but I started to find this necessity, but the unknown public string, and netizen SOHOLI (Tianya Lonely GetLargePublicString is a combination of the entire short string in the long train. It is more advantageous for a time. It has the advantage of a space. I don't know if you have more inspiring. After the SM's interview written test, MS interview interview, finally got a position of SM 发, MS gun's shadow, people have already reminded me to start, but I haven't thought about it, I'm still annoying. !

转载请注明原文地址:https://www.9cbs.com/read-130829.html

New Post(0)