Tag Archives: pen

VIM edit prompt swap file already exists solution

When editing an .ini file on a linux server, it gets stuck and when you close the connection tool and re-enter to work on the .ini file, you are prompted.

E325: ATTENTION
Found a swap file by the name “.xxx.ini.swp”

(1) Another program may be editing the same file. If this is the case,

be careful not to end up with two different instances of the same

file when making changes. Quit, or continue with caution.

(2) An edit session for this file crashed.

If this is the case, use “:recover” or “vim -r other.conf”

to recover the changes (see “:help recovery”).

If you did this already, delete the swap file “.other.conf.swp”

to avoid this message.

Swap file “.xxx.ini.swp” already exists!
[O]pen Read-Only, (E)dit anyway, (R)ecover, (Q)uit, (A)bort:

 

Solution.

Execute the following command in the directory where the file is located.

ls -a

Check the hidden files in the current directory and find the .xxx.ini.swap file

Delete the file by executing the delete command

rm -rf .xxx.ini.swap

Execute vim xxx.ini again and you will not be prompted.

140. Word Break II

Title: 140. Word Break II

Given anon-emptystringsand a dictionarywordDictcontaining a list ofnon-emptywords, add spaces insto construct a sentence where each word is a valid dictionary word.Return all such possible sentences.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.

You may assume the dictionary does not contain duplicate words.

Example 1:

Input:
s = "catsanddog" wordDict = ["cat", "cats", "and", "sand", "dog"] Output: [
 "cats and dog",
 "cat sand dog"
]

Example 2:

Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
 "pine apple pen apple",
 "pineapple pen apple",
 "pine applepen apple"
]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

Input:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
Output:
[]

Thinking of solving problems

In fact, the solution of this problem is the same as 139. Word break. You can refer to the idea of 139. Word break https://my.oschina.net/JiamingMai/blog/4331735 , slightly different from 139. Word break, this question needs to record all the cases in which h [0] [i] is true.

Time complexity analysis

In essence, it is the same as 139. Word break, so the time complexity is O (KN ^ 2), which is a reference for the analysis process https://my.oschina.net/JiamingMai/blog/4331735

Finally realized

java implementation

public class Solution {

    List<String&>[] records;

    private boolean[][] h;

    private boolean[][] r;

    public List<String&> wordBreak(String s, List<String&> wordDict) {
        int n = s.length();
        if (!fastWordBreakInternal(s, wordDict)) {
            return new ArrayList<&>();
        }
        boolean res = wordBreakInternal(s, wordDict);
        if (res) {
            return records[n];
        }
        return new ArrayList<&>();
    }

    public boolean fastWordBreakInternal(String s, List<String&> wordDict) {
        int n = s.length();
        h = new boolean[n+1][n+1];
        r = new boolean[n+1][n+1];
        initR(n, s, wordDict);
        h[0][0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = i; j &>= 0; j--) {
                if (!h[0][i]) {
                    h[0][i] = h[0][i-j] && r[i-j][i];
                } else {
                    break;
                }
            }
        }
        return h[0][n];
    }

    public boolean wordBreakInternal(String s, List<String&> wordDict) {
        int n = s.length();
        h = new boolean[n + 1][n + 1];
        r = new boolean[n + 1][n + 1];
        records = new List[n + 1];
        initR(n, s, wordDict);
        h[0][0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = i; j &>= 0; j--) {
                if (h[0][i - j] && r[i - j][i]) {
                    h[0][i] = true;
                    record(i, j, s);
                }
            }
        }
        return h[0][n];
    }

    private void record(int i, int j, String s) {
        if (null == records[i]) {
            records[i] = new ArrayList<&>();
        }
        String token = s.substring(i - j, i);
        if (null != records[i - j]) {
            for (String str : records[i - j]) {
                StringBuffer sb = new StringBuffer();
                sb.append(str).append(" ").append(token);
                records[i].add(sb.toString());
            }
        }  else {
            records[i].add(token);
        }
    }

    private void initR(int n, String s, List<String&> wordDict) {
        for (int i = 0; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                r[i][j] = r(i, j, s, wordDict);
            }
        }
    }

    private boolean r(int i, int j, String s, List<String&> wordDict) {
        String token = s.substring(i, j);
        for (String word : wordDict) {
            if (word.equals(token)) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        List<String&> wordDict = new ArrayList<&>();
        wordDict.add("a");
        wordDict.add("aa");
        wordDict.add("aaa");
        wordDict.add("aaaa");
        wordDict.add("aaaaa");
        wordDict.add("aaaaaa");
        wordDict.add("aaaaaaa");
        wordDict.add("aaaaaaaa");
        wordDict.add("aaaaaaaaa");
        wordDict.add("aaaaaaaaaa");
        String s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
        Solution solution = new Solution();
        List<String&> res = solution.wordBreak(s, wordDict);
        res.stream().forEach(str -&> {System.out.println(str);});
    }

}

note that in the main method of the code, the input is a continuous string of a with only one B in the middle. In this case, if you record while calculating directly, it will time out. So here’s a trick to quickly determine whether the input string can be disassembled. If not, you can directly output an empty list. This example is just a case that cannot be disassembled.

[leetcode] 140. Word break II word split II

Given anon-emptystringsand a dictionarywordDictcontaining a list ofnon-emptywords, add spaces insto construct a sentence where each word is a valid dictionary word.Return all such possible sentences.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.

You may assume the dictionary does not contain duplicate words.

Example 1:

Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
 "cats and dog",
 "cat sand dog"
]

Example 2:

Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
 "pine apple pen apple",
 "pineapple pen apple",
 "pine applepen apple"
]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

Input:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
Output:
[]

139. Word break is an extension of word break. That question is just to judge whether it can be split, and this question requires the output of all possible split combinations.

Solution: DP + DFS, first use DP to calculate whether it can be split, and then use DFS to find the specific split combination.

Java:

public static List<String&> wordBreak(String s, Set<String&> dict) {
    //create an array of ArrayList<String&>
    List<String&> dp[] = new ArrayList[s.length()+1];
    dp[0] = new ArrayList<String&>();
 
    for(int i=0; i<s.length(); i++){
        if( dp[i] == null ) 
            continue; 
 
        for(String word:dict){
            int len = word.length();
            int end = i+len;
            if(end &> s.length()) 
                continue;
 
            if(s.substring(i,end).equals(word)){
                if(dp[end] == null){
                    dp[end] = new ArrayList<String&>();
                }
                dp[end].add(word);
            }
        }
    }
 
    List<String&> result = new LinkedList<String&>();
    if(dp[s.length()] == null) 
        return result; 
 
    ArrayList<String&> temp = new ArrayList<String&>();
    dfs(dp, s.length(), result, temp);
 
    return result;
}
 
public static void dfs(List<String&> dp[],int end,List<String&> result, ArrayList<String&> tmp){
    if(end <= 0){
        String path = tmp.get(tmp.size()-1);
        for(int i=tmp.size()-2; i&>=0; i--){
            path += " " + tmp.get(i) ;
        }
 
        result.add(path);
        return;
    }
 
    for(String str : dp[end]){
        tmp.add(str);
        dfs(dp, end-str.length(), result, tmp);
        tmp.remove(tmp.size()-1);
    }
}

Java:

public List<String&> wordBreak(String s, Set<String&> wordDict) {
    ArrayList<String&> [] pos = new ArrayList[s.length()+1];
    pos[0]=new ArrayList<String&>();
 
    for(int i=0; i<s.length(); i++){
        if(pos[i]!=null){
            for(int j=i+1; j<=s.length(); j++){
                String sub = s.substring(i,j);
                if(wordDict.contains(sub)){
                    if(pos[j]==null){
                        ArrayList<String&> list = new ArrayList<String&>();
                        list.add(sub);
                        pos[j]=list;
                    }else{
                        pos[j].add(sub);
                    }
 
                }
            }
        }
    }
 
    if(pos[s.length()]==null){
        return new ArrayList<String&>();
    }else{
        ArrayList<String&> result = new ArrayList<String&>();
        dfs(pos, result, "", s.length());
        return result;
    }
}
 
public void dfs(ArrayList<String&> [] pos, ArrayList<String&> result, String curr, int i){
    if(i==0){
        result.add(curr.trim());
        return;
    }
 
    for(String s: pos[i]){
        String combined = s + " "+ curr;
        dfs(pos, result, combined, i-s.length());
    }
} 

Java:

public class Solution {
    Map<String, List<String&>&> done = new HashMap<&>();
    Set<String&> dict;

    public List<String&> wordBreak(String s, Set<String&> dict) {
        this.dict = dict;
        done.put("", new ArrayList<&>());
        done.get("").add("");

        return dfs(s);
    }

    List<String&> dfs(String s) {
        if (done.containsKey(s)) {
            return done.get(s);
        }
        List<String&> ans = new ArrayList<&>();

        for (int len = 1; len <= s.length(); len++) { 
            String s1 = s.substring(0, len);
            String s2 = s.substring(len);

            if (dict.contains(s1)) {
                List<String&> s2_res = dfs(s2);
                for (String item : s2_res) {
                    if (item == "") {
                        ans.add(s1);
                    } else {
                        ans.add(s1 + " " + item);
                    }
                }
            }
        }
        done.put(s, ans);
        return ans;
    }
} 

Python:

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: List[str]
        """
        n = len(s)

        max_len = 0
        for string in wordDict:
            max_len = max(max_len, len(string))

        can_break = [False for _ in xrange(n + 1)]
        valid = [[False] * n for _ in xrange(n)]
        can_break[0] = True
        for i in xrange(1, n + 1):
            for l in xrange(1, min(i, max_len) + 1):
                if can_break[i-l] and s[i-l:i] in wordDict:
                    valid[i-l][i-1] = True
                    can_break[i] = True

        result = []
        if can_break[-1]:
            self.wordBreakHelper(s, valid, 0, [], result)
        return result

    def wordBreakHelper(self, s, valid, start, path, result):
        if start == len(s):
            result.append(" ".join(path))
            return
        for i in xrange(start, len(s)):
            if valid[start][i]:
                path += [s[start:i+1]]
                self.wordBreakHelper(s, valid, i + 1, path, result)
                path.pop() 

C++:

class Solution {
public:
    vector<string&> wordBreak(string s, unordered_set<string&>& wordDict) {
        vector<string&> res;
        string out;
        vector<bool&> possible(s.size() + 1, true);
        wordBreakDFS(s, wordDict, 0, possible, out, res);
        return res;
    }
    void wordBreakDFS(string &s, unordered_set<string&> &wordDict, int start, vector<bool&> &possible, string &out, vector<string&> &res) {
        if (start == s.size()) {
            res.push_back(out.substr(0, out.size() - 1));
            return;
        }
        for (int i = start; i < s.size(); ++i) {
            string word = s.substr(start, i - start + 1);
            if (wordDict.find(word) != wordDict.end() && possible[i + 1]) {
                out.append(word).append(" ");
                int oldSize = res.size();
                wordBreakDFS(s, wordDict, i + 1, possible, out, res);
                if (res.size() == oldSize) possible[i + 1] = false;
                out.resize(out.size() - word.size() - 1);
            }
        }
    }
};

>>

Similar theme:

[LeetCode] 139. Word Break units break

All LeetCode Questions List Total