查找兩個字符之間的子字符串

-2

我需要爲我的作業編寫獲取兩個參數string和char的方法，並且它需要返回以該char開頭並以該char結尾的字符串數。查找兩個字符之間的子字符串

實施例： 對於字符串"abcbcabcacab"和焦炭「C」，則該方法將返回6. （子字符串是"cbc", "cabc", "cac", "cbcabc", "cabcac", "cbcabcac"）

它需要功效成爲可能，而唯一我可以使用的兩種方法是charAt()和length()。這很困難，經過3個小時的努力，我問你們是否有人解決這個問題，或者至少讓我看到一些線索。

來源

2016-01-13 Avishay28

讓我們看看您的代碼到目前爲止。 –

迄今爲止，我在紙上寫下了所有東西，因爲我仍然試圖弄清楚如何解決這個問題。 – Avishay28

紙上的代碼永遠不是一個好主意，因爲它不附帶編譯器。在IDE中給它一個誠實的努力。 –

顯而易見的解決方案是檢查在輸入字符串中的每個符號，如果等於指定的字符，然後試圖找到所有可能的子串，從這個角度出發，像這樣：

long cnt = 0; 
for (int i = 0; i < (s.length() - 1); i++) 
    if (s.charAt(i) == c) 
     for (int j = (i + 1); j < s.length(); j++) 
      if (s.charAt(j) == c) 
       cnt++; 
return cnt;

該解決方案具有複雜度爲O （N^2）

但是，這似乎實際上由在串，字符的出現次數確定子串的數目爲Triangular number

因此，優化的O（N）的解決方案是：

long cnt = -1; 
for (int i = 0; i < s.length(); i++) 
    if (s.charAt(i) == c) 
     cnt++; 
return (cnt * (cnt + 1)) >>> 1;

來源

2016-01-13 19:27:29

感謝您的回答，您能解釋一下「>>> 1」是什麼意思？ – Avishay28

@Avishay28比2更快，所以'>>> 1'可以替換爲'/ 2' –

最簡單的一點就是你應該使用循環。

循環穿過琴絃。檢查當前字符串是否以給定字符開始並以給定字符結束。如果它不只是跳到下一個。如果它只是循環使用1到長度減去第二個字符的計數器。

你會通過踢出無效的字符串，你會減少時間，你會檢查2個字符減少每個字符串;）我想這是一個相當快的方式。

例

// String definition bla String[] myArray 
int count = 0; 
for(int i = 0; i < myArray.length(); i++) { 

    if(myArray[i].charAt(0) == givenChar && myArray[i].charAt(myArray.length()-1)) { 

    for(int j = 1; j < myArray.length()-2;j++) { 

     if(myArray[i].charAt(j) == givenChar) 
     count ++; 

    } 
    } 
}

這就是大概的瞭解。

我正在檢查給定的字符串是否以givenChar開始和結束。如果它再次通過字符串檢查givenChar。如果確實存在，我正在計數1。

我希望可以幫到你;

祝你有美好的一天！

來源

2016-01-13 19:11:13

謝謝。什麼是「myArray []」？這是給出的字符串？ – Avishay28

函數可能看起來像這樣 public（static）int myFunction（String [] myArray，char givenChar）如果函數需要是靜態的，您可以添加標籤，否則刪除。 myArray應包含要檢查的字符串，如您在原始文章中列出的字符串。 –

但函數應該得到字符串和字符，而不是數組。爲什麼要把它放在數組中？只有一個字符串.. – Avishay28

查找兩個字符之間的子字符串

回答

相關問題