1

そのようなアルゴリズムを Java で書こうとしています。文字列入力「abaab」をテストしています。文字列の入力は小文字であると想定しても安全です。

アルゴリズムがどこで間違っているかを確認するのに途方に暮れています (この入力に対して、「ab」と「abaab」ではなく「a a」のみを出力します。何かアイデアはありますか?

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));
    }
4

3 に答える 3

2

これが私の解決策です。最長の部分文字列は常に最初の母音で始まり、最後の子音で終わります。要するに、子音を読むたびに、前の母音までの距離を見て、それが優れているかどうかを確認します。少なくとも母音を 1 つ読むまでは、何もできません。

    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));
}
于 2016-03-02T15:04:00.570 に答える
-1

あなたの実装は非常に複雑だと思います。あなたが捕まえようとしていることがいくつかあります：

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));
    }
}
于 2016-03-02T15:19:25.183 に答える