时间戳

首页 > 解决方案 > 在子字符串之间添加下划线

string - 在子字符串之间添加下划线

问题描述

您将获得一个主字符串和一个子字符串，您需要在该子字符串的开头和结尾附加 _。需要注意的一点是，如果子字符串组合在一起，您需要在第一个实例和最后一个实例之间附加 _ ，如果字符串重叠，也是如此。

例如：

input - main String - testabctesttestdeftestestestxyz
        substring - test

output - _test_abc_testtest_def_testestest_xyz

标签： stringalgorithm

解决方案

这个想法是这样的：

  1. 首先从原始字符串中找到子字符串的所有索引。这里的问题是，一些子字符串可能会继续形成（例如 testestest）。

  2. 要获得连续单词的索引，您必须检查哪些索引重叠或短 1。例如 - 对于您的输入 7 到 14 和 18 到 27 是重叠的。

[[0, 3], [7, 10], [11, 14], [18, 21], [21, 24], [24, 27]]

  1. 现在您可以合并那些重叠的索引。

[[0, 3], [7, 14], [18, 27]]

  1. 一旦你合并它们，完成！:)
  2. 现在您可以根据最终索引将下划线放在字符串之间！

既然你没有提到任何编程语言，我在这里附上java代码！

用于从原始字符串中获取子字符串索引并将索引存储在列表中的函数：

 void checkAndAdd(String s, String t, int index, List<List<Integer>> list) {
    boolean flag = true;
    int len = (s.length() > t.length()) ? t.length() : s.length();
    s = s.substring(index);
    int i, n = t.length();
    /* traverse whole substring, if n (denotes - substring's length) becomes
      0 -- means "substring found" */
    /* if so, add starting index and last index into a list as first_index and 
     last_index*/
    for(i=0; i<len; i++) {
        if(s.charAt(i) != t.charAt(i)) {
            flag = false;
            break;
        }else n--;
    }
    if(flag && n == 0) {
        List<Integer> temp = new ArrayList<Integer>();
        temp.add(index); // start index
        temp.add(i+index-1); // end index
        list.add(temp);
    }
}

现在你必须检查哪些索引是重叠的，如果你发现任何这样的索引只是合并它们：

  void overlappingCloseIndexes(List<List<Integer>> list) {
    int i;      
    for(i=1; i<list.size(); i++) {

        List<Integer> prev = list.get(i-1);
        List<Integer> next = list.get(i);
        /* merge overlapped indexes */
        if(next.get(0) - prev.get(1) == 1 || next.get(0) - prev.get(1) == 0) {
            int last = next.get(1);             
            list.remove(i);
            prev.remove(1);
            prev.add(last);
        }
    }
    List<Integer> prev = list.get(list.size()-2);
    List<Integer> next = list.get(list.size()-1);

    if(next.get(0) - prev.get(1) == 1 || next.get(0) - prev.get(1) == 0) {
        int last = next.get(1);             
        list.remove(list.size()-1);
        prev.remove(1);
        prev.add(last);
    }
}

最后，您可以在索引（子字符串索引）之前和之后附加“_”：

 String append(String s, List<List<Integer>> list) {
    int first = list.get(0).get(0), last = list.get(0).get(1);
    list.remove(0);
    String temp = "";
    int i;
    for(i=0; i<s.length(); i++) {
        // append "_" whenever i == first_index or i == last_index 
        if(i == first) {
            temp += "_";
        }else if(i == last+1){
            temp += "_";
            if(!list.isEmpty()) {
                first = list.get(0).get(0);
                last = list.get(0).get(1);

                list.remove(0);
            }
        }
        temp += s.charAt(i);

    }
    if(i == last+1) {
        temp +="_";
    }
    return temp;
}

这是驱动程序功能：

public static void main(String[] args) {
    String s = "testabctesttestdeftestestestxyz";
    String t = "test";
    List<List<Integer>> list = new ArrayList<List<Integer>>();

    for(int i=0; i<s.length(); i++) {
        if(s.charAt(i) == t.charAt(0)) {
            /* check whenever i-th char from main string match 
             0-th char of substring */
            checkAndAdd(s, t, i, list);
        }
    }
    overlappingCloseIndexes(list);
    s = append(s, list);
    System.out.println(s);
}

注意：从主字符串中找到子字符串索引需要 O(n^2) 复杂度，这是该程序的整体复杂度！

推荐阅读