# 02 公共前缀问题

A 思想

前缀:

  1. 对题目所给数组进行排序(Array.sort)

  2. 设立一个哨兵字符,默认为false(用来判断是否有必要遍历下去)

  3. 设置字符串str,默认为""(来拼接每次遍历得到的公共部分)

  4. 获取排序后的数组的第一个元素并把它拆分成一个个字符串(若数组不是字符串可以先转成字符串)

  5. 对拆分后的字符串数组进行遍历(具体过程如下:)

  6. 若字符串数组的首字母是数组最后一个元素的前缀,那么设置哨兵字符为true,让str拼接字符串数组的首字母,然后一直遍历下去(有就str拼接)直到找到最多的公共前缀,

    若不是,则直接退出循环(首字母不是,后面的必然不符合要求了)

  7. 最后返回字符串str的值

B 实例操作:查找字符串数组中的最高公共前缀

package class01;import java.util.Arrays;public class Solution2 {    public static void main(String[] args) {        String[] strings={"abcb","abcd","abcghc"};        System.out.println(prefix(strings));    }    public static String prefix(String[] strs){      Arrays.sort(strs);      boolean flag=false;        String prefix ="";//初始化          String[] temp=strs[0].split("");//把题目已知的字符串数组的第一个字符串拆分成一个个字符          for (int i = 0; i < temp.length; i++) {              if(strs[strs.length-1].substring(i).startsWith(temp[i])){                  prefix=prefix+temp[i];                  flag=true;//只要有一个前缀,flag1就为true              }              if(flag==false){                  return "";              }          }        return prefix;    }}
赞 (0)

相关推荐