一、概要

　　本文介紹了有關(guān)字符串的算法第一部分的Java代碼實(shí)現(xiàn)，算法目錄：

　　替換字符串中的空格

　　輸入一個(gè)字符串，打印出該字符串的所有排列

　　第一個(gè)只出現(xiàn)一次的字符

　　翻轉(zhuǎn)句子

　　計(jì)算字符串之間的最短距離

　　“二、代碼實(shí)現(xiàn)

　　2.1替換字符串中的空格

　　問(wèn)題描述

　　實(shí)現(xiàn)一個(gè)函數(shù)，將字符串p中的所有空格都替換成為指定的字符串r。

　　解決思路

　　遍歷原始的字符串p，統(tǒng)計(jì)原先字符串中空格的個(gè)數(shù)spaceNum。

　　創(chuàng)建一個(gè)新的數(shù)組n，用于存放替換后的字符串。由于原先字符串中空格也占了一個(gè)位置，因此新數(shù)組n的長(zhǎng)度為p.len+(r.len-1)*spaceNum。

　　對(duì)于p從后往前遍歷，如果遇到了空格，那么就將需要替換的字符串r中的字符從后往前填入n數(shù)組中；如果遇到了非空格，那么就將p中的字符填入n數(shù)組中。

　　實(shí)現(xiàn)代碼

　　運(yùn)行結(jié)果

　　2.2輸入一個(gè)字符串，打印出該字符串的所有排列

　　問(wèn)題描述

　　輸入一個(gè)字符串，打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc，則輸出由字符a、b、c所能排列出來(lái)的所有字符串a(chǎn)bc、acb、bac、bca、cab和cba。

　　解決思路

　　這是一個(gè)遞歸問(wèn)題，求一個(gè)長(zhǎng)度為n的字符串的全排列的方法為：

　　n[0..n.len-1]全排列的計(jì)算方法為：將n[0]位置的字符分別和n[1..n.len-1]的每一個(gè)字符串交換，n[0]和交換后的n[1..n.len-1]的全排列進(jìn)行組合。我們將字符串{s}的全排列表示為{s}，那么對(duì)于abc來(lái)說(shuō)，其全排列{abc}，就等于是a+{bc}、b+{ac}，c+{ba}。

　　以此類推，n[1..n.len-1]的全排列，則是將n[1]分別和n[2..n.len-1]的每一個(gè)字符串交換，再求出交換后的n[2..len-1]的全排列，遞歸結(jié)束的條件為n[i..n.len-1]只有一個(gè)字符，例如，bc的全排列為b+{c}、c+{b}，而{c}和{b}的全排列只有一種，因此遞歸結(jié)束，這時(shí)候就可以打印出結(jié)果。

　　實(shí)現(xiàn)代碼

　　運(yùn)行結(jié)果

　　2.3第一個(gè)只出現(xiàn)一次的字符

　　問(wèn)題描述

　　在字符串中找出第一個(gè)只出現(xiàn)一次的字符。如輸入abaccdeff，則輸出b，要求時(shí)間復(fù)雜度為O(n)。

　　解決思路

　　這里需要采用以空間換時(shí)間的思想，也就是創(chuàng)建一個(gè)足夠大的數(shù)組c，這里為256，然后對(duì)原始的數(shù)組p進(jìn)行兩次遍歷：

　　第一次從頭開(kāi)始遍歷p，以p的值作為數(shù)組c的下標(biāo)，并將c中對(duì)應(yīng)位置的值加1，也就是說(shuō)c[Integer.valueOf(i)]的值表示的是字符i在p中出現(xiàn)的次數(shù)。這和HashMap的原理有些類似，只不過(guò)是將查找的key值直接簡(jiǎn)化成為了value的整型值。

　　第二次從頭開(kāi)始遍歷p，查找數(shù)組c對(duì)應(yīng)位置該值是否為1，如果為1，那么就表示它是第一次只出現(xiàn)一次的字符。

　　實(shí)現(xiàn)代碼

　　運(yùn)行結(jié)果

　　2.4翻轉(zhuǎn)句子

　　問(wèn)題描述

　　翻轉(zhuǎn)句子中單詞的順序，但單詞內(nèi)字符的順序不變，句子中單詞以空格符隔開(kāi)。例如Iamaoriginalstring翻轉(zhuǎn)后的結(jié)果為stringoriginalaamI。

　　解決思路

　　實(shí)現(xiàn)過(guò)程分為兩步：

　　第一步，將整個(gè)句子中的所有字符都翻轉(zhuǎn)

　　第二步，遍歷翻轉(zhuǎn)后的句子，對(duì)于句子內(nèi)的每一個(gè)單詞，將其字符再翻轉(zhuǎn)一次，就能保證單詞內(nèi)字符的順序不變。翻轉(zhuǎn)單詞的時(shí)候，通過(guò)pStart和pEnd記錄每次遇到單詞的起止下標(biāo)，并使用子方法reverseSub對(duì)單詞中的字符進(jìn)行翻轉(zhuǎn)。

　　實(shí)現(xiàn)代碼

　　運(yùn)行結(jié)果為：

　　2.5計(jì)算字符串之間的最短距離

　　問(wèn)題描述

　　假設(shè)我們有兩個(gè)字符串A和B，那么如果想要將字符串A通過(guò)以下三種操作變換成B：刪除、新增和修改，操作步驟的次數(shù)就稱為字符串A和B之間的距離。

　　現(xiàn)在給定兩個(gè)字符串，求這兩個(gè)字符串之間的最短距離。

　　解決思路

　　首先，我們需要先明確一個(gè)前提條件：如果A的長(zhǎng)度為0，那么A和B之間的距離就為B的長(zhǎng)度，反之對(duì)于B也如此。

　　下面，我們?cè)趤?lái)看普通的情況，假如A[0]和B[0]相同，那么A和B之間的距離就為A[1..A.len-1]和B[1..B.len-1]之間的距離；假如A[0]和B[0]不相同，那么想要讓A和B相同，執(zhí)行的操作有以下幾種：

　　刪除A的第一個(gè)字符，然后計(jì)算A[1..A.len-1]和B[0..B.len-1]的距離

　　刪除B的第一個(gè)字符，然后計(jì)算A[0..A.len-1]和B[1..B.len-1]的距離

　　修改A的第一個(gè)字符為B的第一個(gè)字符，然后計(jì)算A[1..A.len-1]和B[1..B.len-1]的距離

　　修改B的第一個(gè)字符為A的第一個(gè)字符，然后計(jì)算A[1..A.len-1]和B[1..B.len-1]的距離

　　增加A的第一個(gè)字符到B第一個(gè)字符之前，然后計(jì)算A[1..A.len-1]和B[0…B.len-1]的距離

　　增加B的第一個(gè)字符到A第一個(gè)字符之前，然后計(jì)算A[0…A,len-1]和B[1..B.len-1]的距離

　　對(duì)于以上這六種情況，其實(shí)最終都可以歸納為經(jīng)過(guò)一次操作，再加上剩下部分的操作次數(shù)，那么我們的接下來(lái)的工作就是求出剩下部分的操作部分的最小值。對(duì)于上面的任意一種情況，經(jīng)過(guò)劃分后A和B的長(zhǎng)度都會(huì)減少，那么最終必然會(huì)達(dá)到我們?cè)谝婚_(kāi)始談到的前提條件：如果A的長(zhǎng)度為0，那么A和B之間的距離就為B的長(zhǎng)度，反之對(duì)于B也如此。

　　實(shí)現(xiàn)代碼

　　運(yùn)行結(jié)果：

　　以上就是動(dòng)力Java培訓(xùn)機(jī)構(gòu)小編介紹的“Java程序員面試字符串算法教程”的內(nèi)容，希望對(duì)大家有幫助，如有疑問(wèn)，請(qǐng)?jiān)诰€咨詢，有專業(yè)老師隨時(shí)為你服務(wù)。