涂鸦移动2020届校招题目一

题目一

给定一个只包含小写字母的字符串，我们通过如下规则分割它：
1.一个片段中包含的字符不允许出现在其他片段内。
2.分割的片段数应尽可能的多。
请实现一个函数，输出分割的片段。
例如：输入aabbbacceddefgkifk 输出为 aabbba cc edde fgkifk

java代码实现

package exer;
import java.util.*;
public class EXER {
    public static void main(String[] args) {
        // 原始字符串
        Scanner sacn = new Scanner(System.in);
        // 输入字符串 nextLine()
        System.out.println("请输入第一个字符串");
        String s=sacn.nextLine();
        mySlipt(s);
    }
    public static void mySlipt(String s) {
        // 存放结果
        List<MyStrInfo> res = new ArrayList<>();
        
        // 初始第一个字符串放入结果		
        MyStrInfo firstInfo = new MyStrInfo();
        firstInfo.setVal(s.substring(0,1));
        firstInfo.setStartIndex(0);
        res.add(firstInfo);
 
        // 从第二个字符开始
        MyStrInfo info;
        String tmp;
        for (int i=1;i<s.length();i++){
            tmp = s.substring(i,i+1);
            int j=0;
            boolean replaceFlg = false;// 字符串重置标记
            for (;j<res.size();j++){
                info = res.get(j);
                // 如果现有对象包含当前字符，则需要将其合并到新字符串中
                if(info.getVal().contains(tmp)){
                    replaceFlg = true;
                    break;
                }
            }
            // 若重置标记打开，则重置字符串
            if (replaceFlg){
                MyStrInfo initInfo = res.get(j);
                // 新字符串起始下标和结束下标
                int newStart = initInfo.getStartIndex();
                int newEnd = i+1;
                // 初始化字符串
                initInfo.setVal(s.substring(newStart,newEnd));
                // 将j之后的对象删除
                for(int k=res.size()-1;k>j;k--){
                    res.remove(k);
                }
            } else {
                // 新字符串，则新增对象
                MyStrInfo initInfo = new MyStrInfo();
                initInfo.setVal(tmp);
                initInfo.setStartIndex(i);
                res.add(initInfo);
            }
        }
        // 结果打印
        for(MyStrInfo t:res){
            System.out.print(t.getVal()+" ");
        }
    }
}
 
class MyStrInfo{
    
    private String val;      // 当前字符串 
    private int startIndex;	 // 当前字符串在原始字符串中的起始下标
 
    public String getVal() {
        return val;
    }
    public void setVal(String val) {
        this.val = val;
    }
    public int getStartIndex() {
        return startIndex;
    }
    public void setStartIndex(int startIndex) {
        this.startIndex = startIndex;
    }
}