輸入一個(gè)字符串，輸出該字符串中對(duì)稱的子字符串的最大長(zhǎng)度
題目：輸入一個(gè)字符串，輸出該字符串中對(duì)稱的子字符串的最大長(zhǎng)度。比如輸入字符串“google”，由于該字符串里最長(zhǎng)的對(duì)稱子字符串是“goog”，因此輸出4。
分析：可能很多人都寫過判斷一個(gè)字符串是不是對(duì)稱的函數(shù)，這個(gè)題目可以看成是該函數(shù)的加強(qiáng)版。
要判斷一個(gè)字符串是不是對(duì)稱的，不是一件很難的事情。我們可以先得到字符串首尾兩個(gè)字符，判斷是不是相等。如果不相等，那該字符串肯定不是對(duì)稱的。否則我們接著判斷里面的兩個(gè)字符是不是相等，以此類推?；谶@個(gè)思路，我們不難寫出如下代碼：
////////////////////////////////////////////////////////////////
// Whether a string between pBegin and pEnd is symmetrical?
////////////////////////////////////////////////////////////////
bool?IsSymmetrical(char* pBegin,?char* pEnd)
{
???????if(pBegin == NULL || pEnd == NULL || pBegin > pEnd)
??????????????return?false;
?
???????while(pBegin < pEnd)
???????{
??????????????if(*pBegin != *pEnd)
?????????????????????return?false;
?
??????????????pBegin++;
??????????????pEnd --;
???????}
?
???????return?true;
}
要判斷一個(gè)字符串pString是不是對(duì)稱的，我們只需要調(diào)用IsSymmetrical(pString, &pString[strlen(pString) – 1])就可以了。
現(xiàn)在我們?cè)囍鴣淼玫綄?duì)稱子字符串的最大長(zhǎng)度。最直觀的做法就是得到輸入字符串的所有子字符串，并逐個(gè)判斷是不是對(duì)稱的。如果一個(gè)子字符串是對(duì)稱的，我們就得到它的長(zhǎng)度。這樣經(jīng)過比較，就能得到最長(zhǎng)的對(duì)稱子字符串的長(zhǎng)度了。于是，我們可以寫出如下代碼：
////////////////////////////////////////////////////////////////
// Get the longest length of its all symmetrical substrings
// Time needed is O(T^3)
////////////////////////////////////////////////////////////////
int?GetLongestSymmetricalLength_1(char* pString)
{
???????if(pString == NULL)
??????????????return?0;
?
???????int?symmeticalLength = 1;
?
???????char* pFirst = pString;
???????int?length = strlen(pString);
???????while(pFirst < &pString[length - 1])
???????{
??????????????char* pLast = pFirst + 1;
??????????????while(pLast <= &pString[length - 1])
??????????????{
?????????????????????if(IsSymmetrical(pFirst, pLast))
?????????????????????{
???????????????????????????int?newLength = pLast - pFirst + 1;
???????????????????????????if(newLength > symmeticalLength)
??????????????????????????????????symmeticalLength = newLength;?????????????????????????
?????????????????????}
?
?????????????????????pLast++;
??????????????}
?
??????????????pFirst++;
???????}
?
???????return?symmeticalLength;
}
我們來分析一下上述方法的時(shí)間效率。由于我們需要兩重while循環(huán)，每重循環(huán)需要O（n）的時(shí)間。另外，我們?cè)谘h(huán)中調(diào)用了IsSymmetrical，每次調(diào)用也需要O（n）的時(shí)間。因此整個(gè)函數(shù)的時(shí)間效率是O（n3）。
通常O（n3）不會(huì)是一個(gè)高效的算法。如果我們仔細(xì)分析上述方法的比較過程，我們就能發(fā)現(xiàn)其中有很多重復(fù)的比較。假設(shè)我們需要判斷一個(gè)子字符串具有aAa的形式（A是aAa的子字符串，可能含有多個(gè)字符）。我們先把pFirst指向最前面的字符a，把pLast指向最后面的字符a，由于兩個(gè)字符相同，我們?cè)贗sSymtical函數(shù)內(nèi)部向后移動(dòng)pFirst，向前移動(dòng)pLast，以判斷A是不是對(duì)稱的。接下來若干步驟之后，由于A也是輸入字符串的一個(gè)子字符串，我們需要再一次判斷它是不是對(duì)稱的。也就是說，我們重復(fù)多次地在判斷A是不是對(duì)稱的。
造成上述重復(fù)比較的根源在于IsSymmetrical的比較是從外向里進(jìn)行的。在判斷aAa是不是對(duì)稱的時(shí)候，我們不知道A是不是對(duì)稱的，因此需要花費(fèi)O（n）的時(shí)間來判斷。下次我們判斷A是不是對(duì)稱的時(shí)候，我們?nèi)匀恍枰狾（n）的時(shí)間。
如果我們換一種思路，我們從里向外來判斷。也就是我們先判斷子字符串A是不是對(duì)稱的。如果A不是對(duì)稱的，那么向該子字符串兩端各延長(zhǎng)一個(gè)字符得到的字符串肯定不是對(duì)稱的。如果A對(duì)稱，那么我們只需要判斷A兩端延長(zhǎng)的一個(gè)字符是不是相等的，如果相等，則延長(zhǎng)后的字符串是對(duì)稱的。因此在知道A是否對(duì)稱之后，只需要O（1）的時(shí)間就能知道aAa是不是對(duì)稱的。
我們可以根據(jù)從里向外比較的思路寫出如下代碼：
////////////////////////////////////////////////////////////////
// Get the longest length of its all symmetrical substrings
// Time needed is O(T^2)
////////////////////////////////////////////////////////////////
int?GetLongestSymmetricalLength_2(char* pString)
{
???????if(pString == NULL)
??????????????return?0;
?
???????int?symmeticalLength = 1;
??????
???????char* pChar = pString;
???????while(*pChar !=?'/0')
???????{
??????????????// Substrings with odd length
??????????????char* pFirst = pChar - 1;
??????????????char* pLast = pChar + 1;
??????????????while(pFirst >= pString && *pLast !=?'/0'?&& *pFirst == *pLast)
??????????????{
?????????????????????pFirst--;
?????????????????????pLast++;
??????????????}
?
??????????????int?newLength = pLast - pFirst - 1;
??????????????if(newLength > symmeticalLength)
?????????????????????symmeticalLength = newLength;
?
??????????????// Substrings with even length
??????????????pFirst = pChar;
??????????????pLast = pChar + 1;
??????????????while(pFirst >= pString && *pLast !=?'/0'?&& *pFirst == *pLast)
??????????????{
?????????????????????pFirst--;
?????????????????????pLast++;
??????????????}
?
??????????????newLength = pLast - pFirst - 1;
??????????????if(newLength > symmeticalLength)
?????????????????????symmeticalLength = newLength;
?
??????????????pChar++;
???????}
?
???????return?symmeticalLength;
}
由于子字符串的長(zhǎng)度可能是奇數(shù)也可能是偶數(shù)。長(zhǎng)度是奇數(shù)的字符串是從只有一個(gè)字符的中心向兩端延長(zhǎng)出來，而長(zhǎng)度為偶數(shù)的字符串是從一個(gè)有兩個(gè)字符的中心向兩端延長(zhǎng)出來。因此我們的代碼要把這種情況都考慮進(jìn)去。
在上述代碼中，我們從字符串的每個(gè)字符串兩端開始延長(zhǎng)，如果當(dāng)前的子字符串是對(duì)稱的，再判斷延長(zhǎng)之后的字符串是不是對(duì)稱的。由于總共有O（n）個(gè)字符，每個(gè)字符可能延長(zhǎng)O（n）次，每次延長(zhǎng)時(shí)只需要O（1）就能判斷出是不是對(duì)稱的，因此整個(gè)函數(shù)的時(shí)間效率是O（n2）。
下載文檔
