快捷導(dǎo)航

算法練習(xí)之從String.indexOf的模擬實現(xiàn)開始

更新時間：2014年12月25日 14:24:28 投稿：mdxy-dxy

這篇文章主要介紹了算法練習(xí)從String.indexOf的模擬實現(xiàn)開始,需要的朋友可以參考下

String.indexOf的模擬實現(xiàn)，沒想象中有多么高深的查找算法，就是最普通的遍歷查找

思路：先找到第一個相同的字符，然后依次比較后面的字符，若都相等則表示查找成功

/** 
   * 查找字符串pattern在str中第一次出現(xiàn)的位置 
   * @param str 
   * @param pattern 
   * @return 
   */ 
  public int firstIndexOf(String str, String pattern) { 
    for (int i = 0; i < (str.length() - pattern.length()); i++) { 
      int j = 0; 
      while (j < pattern.length()) { 
        if (str.charAt(i + j) != pattern.charAt(j)) break; 
        j++; 
      } 
      if(j==pattern.length()) return i; 
    } 
    return -1; 
  } 
 
  /** 
   * 查找字符串pattern在str中最后一次出現(xiàn)的位置 
   * @param str 
   * @param pattern 
   * @return 
   */ 
  public int lastIndexOf(String str, String pattern) { 
    for (int i = str.length() - pattern.length(); i >= 0; i--) { 
      int j = 0; 
      while (j < pattern.length()) { 
        if (str.charAt(i + j) != pattern.charAt(j)) break; 
        j++; 
      } 
      if (j == pattern.length()) return i; 
    } 
    return -1; 
  } 
 
  /** 
   * 查找字符串pattern在str中出現(xiàn)的位置 
   * @param str 
   * @param pattern 
   * @return 
   */ 
  public List<Integer> indexOf(String str, String pattern) { 
    List<Integer> indexs = new ArrayList<Integer>(); 
    for (int i = 0; i < (str.length() - pattern.length()); i++) { 
      int j = 0; 
      while (j < pattern.length()) { 
        if (str.charAt(i + j) != pattern.charAt(j)) break; 
        j++; 
      } 
      if (j == pattern.length()) indexs.add(i); 
    } 
    return indexs; 
  }

同樣更常用的String.contains方法實際上就是調(diào)用的String.indexOf實現(xiàn)

/** 
   * 判斷字符串pattern在str中是否存在 
   * @param str 
   * @param pattern 
   * @return 
   */ 
  public boolean contains(String str, String pattern) { 
    return firstIndexOf(str, pattern) != -1; 
  }