我知道 substring 是如何工作的，但我試圖了解它在下面的代碼中是如何工作的。目標(biāo)是在字符串?dāng)?shù)組中找到最長(zhǎng)的公共前綴。輸入的字符串是 {flower, flow, fleece}?？雌饋?lái) substring 每次都只是取花的整個(gè)詞，當(dāng)它不為 0 時(shí)，因?yàn)?0 到 length-1 將給出整個(gè)詞。 public String longestCommonPrefix(String[] strs) { if (strs.length == 0) return ""; String prefix = strs[0]; for (int i = 1; i < strs.length; i++) while (strs[i].indexOf(prefix) != 0) { prefix = prefix.substring(0, prefix.length() - 1); if (prefix.isEmpty()) return ""; } return prefix;}輸出為 fl。我只是想了解為什么。
3 回答
蝴蝶刀刀
TA貢獻(xiàn)1801條經(jīng)驗(yàn) 獲得超8個(gè)贊
0 到 length-1 將給出整個(gè)單詞
不，它返回除最后一個(gè)字符之外的單詞。
來(lái)自：https://docs.oracle.com/javase/7/docs/api/java/lang/String.html#substring(int,%20int)
public String substring(int beginIndex, int endIndex)
返回一個(gè)新字符串，它是該字符串的子字符串。
子字符串從指定的 beginIndex 開始并擴(kuò)展到索引 endIndex - 1 處的字符。
所以代碼所做的是在每次迭代時(shí)用這一行修剪最后一個(gè)字符：
prefix = prefix.substring(0, prefix.length() - 1);
直到找到一個(gè)共同的前綴。
呼喚遠(yuǎn)方
TA貢獻(xiàn)1856條經(jīng)驗(yàn) 獲得超11個(gè)贊
substring() 中的 endIndex 是唯一的。因此，代碼所做的是從前綴變量中刪除最后一個(gè)字符。
String hello = "hello";
System.out.println(hello.substring(0,hello.length));
// hello
System.out.println(hello.substring(0,hello.length - 1));
// hell
有只小跳蛙
TA貢獻(xiàn)1824條經(jīng)驗(yàn) 獲得超8個(gè)贊
雖然這不是您要問(wèn)的直接問(wèn)題，但值得一提的是，使用indexOfandsubstring并不是解決此問(wèn)題的好方法。
strs[i].indexOf(prefix) != 0是檢查字符串是否以某物開頭的低效方法。這是因?yàn)槿绻l(fā)現(xiàn)字符串不是以 開頭prefix，它會(huì)繼續(xù)在其他位置搜索匹配項(xiàng) - 如果它出現(xiàn)在那里并不重要。
更有效的檢查是!strs[i].startsWith(prefix)：一旦發(fā)現(xiàn)字符串不以前綴開頭，它就會(huì)停止。
然后，使用substring從字符串末尾截?cái)嘁粋€(gè)字符也是低效的：每次截?cái)嘁粋€(gè)字符，都會(huì)創(chuàng)建一個(gè)新字符串，然后您再次檢查；但是在找到匹配的前綴之前，您可能必須砍掉很多單獨(dú)的字符。
您可以通過(guò)使用 來(lái)避免“創(chuàng)建對(duì)象”這一點(diǎn)strs[i].regionMatches(0, prefix, 0, someLength)，其中someLength是一個(gè)從 開始的 int prefix.length()，然后遞減直到regionMatches返回 true。但這仍然是低效的，因?yàn)槟淮芜f減它。
如果您以另一種方式進(jìn)行操作會(huì)更容易：someLength從零開始，然后遞增直到：
它等于 的長(zhǎng)度
prefix：someLength >= prefix.length()它等于 的長(zhǎng)度
strs[i]：someLength >= strs[i].length()該位置的相應(yīng)字符不匹配：
prefix.charAt(someLength) != strs[i].charAt(someLength)
這基本上就是startsWith這樣做的，但是通過(guò)“你自己”做，你會(huì)發(fā)現(xiàn)字符串不同的位置。
然后，用prefix = prefix.substring(0, someLength);它一次剁碎?；蛘吒静豢乘耗憧梢院?jiǎn)單地存儲(chǔ)公共前綴的長(zhǎng)度，并在最后做一次子串。
代碼看起來(lái)像：
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) return "";
int prefixLength = strs[0].length();
for (int i = 1; i < strs.length; i++) {
int s = 0;
while (s < prefixLength
&& s < strs[i].length()
&& strs[0].charAt(s) == strs[i].charAt(s)) {
++s;
}
prefixLength = s;
}
return strs[0].substring(0, prefixLength);
}
添加回答
舉報(bào)
0/150
提交
取消