java - java - 如何从字符串列表中找到最长的公共后缀并在java中返回结果后缀长度？

Question

在 ArrayList 或 LinkedList 中考虑以下内容： [Gloucestershire, Hampshire, Yorkshire, Lancashire] shire 是长度为 5 的最长公共后缀。输出应该是 5 如何编写方法来实现上述和返回长度

Answer 1

尝试这个。
解释在评论中

package javaapplication1;
public class SegmentTree {

    public static void main(String[] args) {
        String[] array = {"Gloucestershire", "Hampshire", "Yorkshire", "Lancashire"};
        int i,j;
        int min=10000000;

        //reversing the strings and finding the length of smallest string
        for(i=0;i<(array.length);i++)
        {
          if(array[i].length()<min)
              min=array[i].length();


         StringBuilder input1 = new StringBuilder();
         input1.append(array[i]);
         array[i] = input1.reverse().toString();
        }

        //finding the length of longest suffix

        for(i=0;i<min;i++)
        {
          for(j=1;j<(array.length);j++)
          {
              if(array[j].charAt(i)!=array[j-1].charAt(i))
              {
                break;
              }
          }
          if(j!=array.length)
              break;
        }

        System.out.println(i);
    }
}

我在这里做的是，首先检查所有字符串的最后一个元素，然后是第二个，依此类推。

时间复杂度： O(n*m)，
n=字符串数，m=最小字符串的长度

Answer 2

Guava 有一个名为的辅助函数Strings.commonSuffix(CharSequence a, CharSequence b)，可以在您的算法中使用。我知道添加像 Guava 这样的依赖项只是为了拥有这个功能可能是矫枉过正 - 在这种情况下，您可以查看源代码以了解此功能是如何实现的，您可以将此实现移动到您的程序中。那么你的程序可能如下所示：

import com.google.common.base.Strings;

import java.io.IOException;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class CommonSuffixLengthMain {

    public static void main(String[] args) throws IOException {

        assert 5 == commonSuffixLength(Arrays.asList("Gloucestershire", "Hampshire", "Yorkshire", "Lancashire"));

        assert 2 == commonSuffixLength(Arrays.asList("abc", "dbc", "qebc", "webc"));

        assert 0 == commonSuffixLength(Collections.emptyList());

        assert 0 == commonSuffixLength(Collections.singletonList("abc"));

        assert 0 == commonSuffixLength(Arrays.asList("abc", "def", "zxc"));
    }

    private static int commonSuffixLength(final List<String> strings) {
        int result = 0;

        if (strings == null || strings.size() < 2) {
            return result;
        }

        for (int i = 0; i < strings.size() - 1; i++) {
            String prefix = Strings.commonSuffix(strings.get(i), strings.get(i + 1));
            result = result == 0 ?
                    prefix.length() :
                    Math.min(prefix.length(), result);
        }

        return result;
    }
}