算法，吐出最小和最大的子字符串，以元音開始，並以字母串輔音結尾

Question

我想用Java編寫這樣的算法。我正在測試字符串輸入「abaab」。假設字符串輸入爲小寫是安全的。

我在檢查在我的算法是怎麼了虧損（僅輸出「AA」此輸入，而不是「AB」和「abaab」。任何想法？

static void SmallestAndLargestSubstring(String input) { 

     char[] vowels = { 'a', 'e', 'i', 'o', 'u' }; 
     char[] cons = { 'b', 'c', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'n', 'p', 'q', 'r', 's', 't', 'v', 'w', 'x', 
       'y', 'z' }; 
     char[] charArray = input.toLowerCase().toCharArray(); 
     int startIndex = 0; 
     int shortEndIndex = 0; 
     int longEndIndex = 0; 
     int large = longEndIndex - startIndex; 
     int small = shortEndIndex - startIndex; 
     ArrayList<Integer> start = new ArrayList<Integer>(); 
     ArrayList<Integer> end = new ArrayList<Integer>(); 

     outerloop: for (int i = 0; i < charArray.length; i++) { 
      for (int z = 0; z < vowels.length; z++) { 
       if (charArray[i] == vowels[z]) { 
        startIndex = i; 
        start.add(startIndex); 
        if (longEndIndex - startIndex > large) { 
         large = longEndIndex - startIndex;     
        } 
        if(longEndIndex - startIndex <= large){ 
         shortEndIndex=start.get(start.size()-1); 
        } 
        if (shortEndIndex - startIndex < small) { 
         small = shortEndIndex - startIndex; 
        } 
        if(shortEndIndex - startIndex >=small){ 
         shortEndIndex=start.get(start.size()-1); 
        } 


        continue outerloop; 
       } 
      } 
      for (int j = 0; j < cons.length; j++) { 
       if (charArray[i] == cons[j]) { 
        longEndIndex = i; 
        shortEndIndex = i; 
        end.add(longEndIndex); 
        if (longEndIndex - startIndex > large) { 
         large = longEndIndex - startIndex; 
        }if(longEndIndex - startIndex <= large){ 
         longEndIndex=end.get(end.size()-1); 
        } 
        if (shortEndIndex - startIndex < small) { 
         small = shortEndIndex - startIndex;      
        }    
        if(shortEndIndex - startIndex >=small) { 
         shortEndIndex=end.get(end.size()-1); 
        } 
        continue outerloop; 
       } 
      } 
     } 


     System.out.println(input.substring(startIndex, shortEndIndex)); 
     System.out.println(input.substring(startIndex, longEndIndex)); 
    } 

Answer 1

這裏是我的解決方案：最長的子串總是以第一個元音開始，以最後一個輔音結束 對於最短的，每次我讀輔音時，我都會看到前一個元音的距離，看看它是否更好 你可以' t做任何事情，直到你閱讀至少一個元音。

static void SmallestAndLargestSubstring(String input) { 

    char[] vowels = { 'a', 'e', 'i', 'o', 'u' }; 
    char[] cons = { 'b', 'c', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'n', 'p', 'q', 'r', 's', 't', 'v', 'w', 'x', 
      'y', 'z' }; 
    char[] charArray = input.toLowerCase().toCharArray(); 
    int longStartIndex=0; 
    int shortStartIndex=0; 
    int shortEndIndex=0; 
    int longEndIndex=0; 
    boolean findVowel = false; 
    int bestStart = 0; 
    int bestEnd = 0; 
    int shortest =Integer.MAX_VALUE; 

    for (int i = 0; i < charArray.length; i++) { 
     for (int z = 0; z < vowels.length; z++) { 
      if (charArray[i] == vowels[z]) { 
       if (!findVowel){ 
        // if this is the first vowel we see 
        longStartIndex = i; 
        shortStartIndex=i; 
        findVowel = true; 
       } 
       else { 
        shortStartIndex = i; 
       } 
      } 
     } 
     for (int j = 0; j < cons.length; j++) { 
      if (charArray[i] == cons[j]) { 
       if (findVowel){ 
        // if we have seen any vowel, this consonant is useless 
        longEndIndex = i; // this one is always than the previous for the largest 
        shortEndIndex = i; // we have to check if this one is better or not 
        if (shortEndIndex-shortStartIndex<shortest){ 
         bestStart = shortStartIndex; 
         bestEnd = shortEndIndex; 
         shortest = shortEndIndex-shortStartIndex; 
        } 
       } 
      } 
     } 
    } 
    System.out.println(input.substring(bestStart, bestEnd+1)); 
    System.out.println(input.substring(longStartIndex, longEndIndex+1)); 
} 

Answer 2

我覺得你的實現過於複雜。有幾件事你試圖抓住：

1）從元音到輔音的最小子字符串：這將是2個字符或0個字符長。

2）從一個元音到輔音的最長子串：這將是從第一個元音到輔音最後的距離，假設一個元音來輔音之前 - 0

否則的長度下面是一個例子實現無串錯誤檢查：

import java.util.*; 

public class cons { 
    public static void main(String...args) 
    { 
     String str = "abaab"; 

     char[] vowels = { 'a', 'e', 'i', 'o', 'u' }; 
     char[] cons = { 'b', 'c', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'n', 'p', 'q', 'r', 's', 't', 'v', 'w', 'x', 
      'y', 'z' }; 

     int firstVowel = -1,lastConsonant = -1; 
     int consVowel = -1; 
     ArrayList<Character> vowel, con; 

     //I use lists for the .contains() method. 

     con = new ArrayList<Character>(); 
     vowel = new ArrayList<Character>(); 

     for (Character c : vowels) 
      vowel.add(c); 
     for (Character c : cons) 
      con.add(c); 

     //Algorithm starts here 
     for(int i = 0; i < str.length() - 1; i++) 
     { 
      //position i is a vowel 
      if (vowel.contains(str.charAt(i))) 
      { 
       //if first vowel isn't set, set it 
       if (firstVowel == -1) 
        firstVowel = i; 
       if (!vowel.contains(str.charAt(i+1))) 
       { 
        consVowel = i; 
        lastConsonant = i+1; 
       } 
      } else { //Otherwise it's a consonant. 
       lastConsonant = i; //set last consonant 
      } 
     } 

     System.out.println(str.substring(firstVowel,lastConsonant)); 
     System.out.println(str.substring(consVowel, consVowel+2)); 
    } 
}