1

我正在尝试用 Java 编写这样的算法。我正在测试字符串输入“abaab”。假设字符串输入为小写字母是安全的。

我在检查我的算法哪里出错时不知所措（它只为此输入输出“a a”而不是“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));
    }
4

3 回答 3

4

我偶然发现了这个问题，寻找同样的问题。

当前接受的答案是错误的。

对于 string uauubbiox，接受的答案中的程序输出：

ub
uauubbiox

这是错误的（正确答案是auuband uubbiox。）即使对于 OP 问题中的情况，该程序也会给出错误答案（abaab而不是baab）。

解决这个问题的正确方法是使用后缀数组。这是一个伪代码，我相信它会为这个问题产生正确的输出：

given string s as input
sa = suffix_array(s)
savf = the first string in sa which starts with a vowel
smallest substring = savf.substring(0, index of first consonant)

savl = the last string in sa which starts with a vowel
smallest substring = savf.substring(0, index of lastconsonant)

让我们试试这个测试字符串。测试字符串的后缀数组是：

0 auubbiox
1 bbiox
2 biox
3 iox
4 ox
5 uauubbiox
6 ubbiox
7 uubbiox

以元音开头的最小字典字符串是：

auubbiox

我们只需要在这个以辅音结尾的字符串中找到最小的前缀。那将是b上述字符串的第 3 位。因此，以元音开头并以辅音结尾的字典上最小的字符串是：

auub

对于另一个字符串，查看后缀数组中以元音开头的最大字符串。那是索引 7 处的字符串：

uubbiox

由于我们想要尽可能大的字符串，我们应该选择以辅音结尾的最长可能前缀。在这种情况下，这将是上面的整个字符串。因此，以元音开头并以辅音结尾的字典序上最大的字符串是：

uubbiox

计算字符串的后缀数组可以在 O(n) 中完成。维基百科文章讨论了一些构建它的方法。互联网上也有一些巧妙的技术可以使创建一个相对容易编码和实现的技术。我喜欢这个给后缀数组提供了一种非常直截了当且易于理解的技术，具有可接受的（在大多数情况下）时间复杂度 O(nlog^2(n))

于 2018-10-07T06:26:57.570 回答
2

这是我的解决方案：最长的子串总是以第一个元音开头，以最后一个辅音结尾。最短，每次读一个辅音，我都会看一下到前一个元音的距离，看看是否更好。在你至少读到一个元音之前，你什么都做不了。

    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 回答